Pathfinding Engine Testing...

[the7trumpets 10]

Welcome to the new home of all things pathfinding related.

This thread will cover the following:

1 - Experiments, hypothesis, and discoveries about the current pathfinding engine for sims walking and driving to work.

2 - Presentation of ideas and testing on alternate algorithms the pathfinding engine could use.

It will NOT include anything about pathfinding for mass transit.  For now, keep that in the "Mass transit testing..." thread.


Thats all folks.  Have fun,  and good luck!!!

[Abby Normal 0]

This is a quick repost of the links I had found previously that seem to be good. Amit''s page in particular is extremely informative. I''m reposting this mostly for my own convenience when I start testing pathfinding theories

1. Java A* Demonstration
2. A* Pathfinding for Beginners

 

[Abby Normal 0]

Hey, I need some help here. For some reason I cannot see the sims going TO work, only coming home FROM work, which, as we''ve previously established is not a valid estimation of their pathing. I have no idea what my computer''s problem is, but I was thinking that perhaps the problem is with the layout itself. Can someone else reproduce this road layout and see if anyone goes to xxxxxxx work?

 

 

On the way to work they all use their personal star trek teleporter device, and they must work at a car factory because they drive home every day using the lower inside route. Help!

[Proper_Bo 0]

Well here is the results you requested.

Identical setup

 

This is on the way TOO work. (the sim at work went the same road but opposite side)

 

 

And this is on the way HOME. (man and black woman took same road as too work, white woman takes same road opposite side)

 

 

Commute time was 21 same as you, and like I said. Identical setup.

 

This may sound like a stupid question, but how do you turn the grid on?

 

Hope this helps you Abby.

[Sharr 6]

Sorry that I don''t have screenshots to support this, but I think the sims like to take a circular route to work and home. They don''t backtrack the way they came unless there is no choice. I saw this when dispatching the fire engine. No matter where I sent it, it never went back the way it came. It found the shortest way there (or close to it), but going back it took whatever scenic route there was. I don''t know what implications that has on the game... but I was thinking that I would hate to be a resident where I sent that fire truck.

[the7trumpets 10]

Turn the grid on by pressing "g"

 

Hey abby, glad to see you got your test up.  In my experience, I have never seen the automata commuting from home to work, only from work to home (I think).  I''ll let you know if I ever see them commuting to work though.  I think it may be more just the way the automata works.

 

I''m looking forward to your conclusions, and why you chose this test though.

[Karybdis 34]

Well the automata do not represent the Pathfinding engine completely.

 

They''re just a calculated representation of the generalized idea of what the pathfinding engine is doing

 

IE someone may be using road a) and road b), however only road b) will show traffic visibly because it has 2 instead of 1 person on it. It likes to do only things that are very noticable visibly. Maybe that''s why you dont see them going there

[the7trumpets 10]

one more thing about automata -

 

While I usually see the automata driving from work to home, they always are driving on the path that the sim is taking to get TO work.  But, as this is a "always does this" situation, it''s impossible to prove.  This is just what I have observed so far.  Let me know if it''s disproven.

[Proper_Bo 0]

Its like I wasnt even here. Incase you didnt read my last thread......

 

 

SAME SETUP as Abby. This time all GO TO WORK on the same road. Before the sims move, several other cars were seen to take the two roads that the sims seem to chose between.

[the7trumpets 10]

I believe it was verified in "travel time testing" that if both routes are identical (miror images of each other), even just at the beginning of the commute, the sims will randomly switch between the two about every 6 months.

 

So, I think which ''miror image'' route they choose doesn''t matter too much.

[the7trumpets 10]

Just to give you guys a teaser... This weekend I''m going to post something I''ve been working on, basically describing vertex(intersection node) based A*, and how it could be the best thing for SC4.  I think it holds extreme promise, but I haven''t finished all the screens yet, and I''m pretty busy.  I''ll probably post it some time this weekend though.

[DarkMatter 21]

Hey guys. Just thought I''d pop my head in and give you a progress report on the pathfinding test program. I got a lot of progress done today, but it still doesn''t have any algorithms. Thats the next step, and I''m brainstorming how to accomplish it. Once this thing is done, it should let you guys test and compare different kinds of algorithms. I don''t know if anyone else here has programming experience, but I may need some help on a few things. For one, I''m not a graphics expert, and this thing renders pretty slow, and very slow if you zoom out to a grid size of 8 (i recommend 16 or 32 for performance reasons right now). Anyway, here is a screenshot, and attached is the first version (its only 40k, but you need to download the .NET Framework to run it, wich is about 20megs. http://www.microsoft.com/downloads/details.aspx?FamilyId=D7158DEE-A83F-4E21-B05A-009D06457787&displaylang=en).

 

[the7trumpets 10]

hey DarkMatter, the program looks GREAT!!!

 

Thanks for working on that, I know it''s alot of work.

 

By the way, don''t let this get in your way of continuing the "guts" of the program, but since we more than likely will be drawing maps inside this program, it might be nice to have a click and drag straight line road thing.  Right now it follows the mouse if the button is pushed down, laying a tile of the selected type for every tile you cross.  I''m talking more about a draw the line out and when you let go of the mouse button it lays the tiles sort of thing.

 

But, PLEASE don''t let this get in the way of the guts, I''m working on developing my understanding on how node-based A* would work for SC4.  Is there a particular way I should start coding it?  Not a big deal, as I haven''t started yet, and have some more ''thinking'' to do before I''m really happy with the way it works, but I was just wondering.

[DarkMatter 21]

I actually have plans to use "rubber-band" style drawing, but its complicated. I have to calculate a start and end point, then calculate all the tiles that the line crosses. As of now, I have absolutely no idea how to do that. But, its one of the things I do intend to do. I actually plan to have a few different drawing modes. Follow, Rubberband, and Fill. They are pretty self explanitory. I''m really concerned about performance though. I just learned that .NET''s graphics library, GDI+, is not hardware accelerated. I can get around this, but I have to rewrite my drawing code.

 

About your algorithm. I don''t want to hold you back from writing it, but....I am working on a standard way to write them so they will work with my program. For one, you should write it as a class (or as an object), rather than as procedural code. If you write the thing in Visual Basic or C++, I can convert it later. C++ would be the better choice. But basically, what I''m doing is creating a set of interfaces, which is just a collection of functions a class is required to implement. These functions will allow me to plug the algorithm into my program and do certain things with it. For example, each algorithm will have a Run(TileMap map) function. This function takes the map you designed, finds any start/destination pairs, and tries to find a path between the two. How you go about finding the path is up to you, but you must write a Run function so I can use it in my program. I''ll have an example of this soon, along with all my source code. Anyone who wishes to improve upon my meager attempts at this is free to do so. The code will be posted at http://www20.brinkster.com/archon777/projects_sc4paths.aspx. I''ve got about an hour before I have to go to work, and I''ll see what I can come up with before that. Otherwise, I''ll finish working on the algorithm requirements later tonight (hmm, MUCH later, actually....12am is the opening of Matrix: Reloaded!! )

[Abby Normal 0]

Hrm. I know for sure when I was doing my series of tests here on page 5 (The series of tests with the orange and green glowing paths) the automata were going to work as well as coming home. I am unwilling to use the MySim automata as I think it is unreliable and misleading for testing commute times, as several of the tests show that the path the MySim was taking was drastically longer than the path the traffic automata were taking and the actual commute time supported the traffic automata as being accurate. It IS possible that the MySim RETURN TRIP is the same as the traffic TO trip, but more testing needs to be done to verify this. Regardless, there definitely was traffic automata going TO work previously, where there is none now. They''d usually start leaving for work around 5am. To sum things up a bit for me:

• MySim is completely unreliable as a traffic pathing indicator (except for the slight possibility of the return trip being accurate to the going trip of normal traffic)
• We have previously proven that the RETURN trip of normal traffic automata is also useless for providing pathing info, as they will return by random paths (the circular commute idea is interesting, however it''s kinda stupid if they did it that way. I don''t really travel a circular route to get to work, I just go back the way I came).
• I believe there is a different mechanism at work for "Special" automata and "normal" automata. I would bet that the MySims use the same pathing as the fire trucks, so if you''re waiting till 6am for the jerk to leave for work, you can probably accomplish things faster using a fire station. Unfortunately, the info won''t be very useful for applying to commute times.

Lastly, I do apologize if this post seems a little terse. Work is pissing me off, there''s a shitload of things to do, and of course I''m the one to do it. Ugh. There is a TON of information in the original travel time testing post, and it''s a lot to go through. Seven, if you have a condensed version of our testing observations and ideas, perhaps it would be a good thing to put in the top of each thread. Or even better, make a mini-commute testing handbook and Dirk can stick it on the articles or references section and you can just link to it in the first post of each of your new threads. I''ll try to jot down little things I''ve noticed as well, but E3 is making work a real pain in the ass and it may be a couple day before I can send you anything.

And I''m frustrated by my teleporting automata ;>

Remember to have fun!!!! I have a couple more tests but I need to figure out why I''m not seeing the automata anymore :/

[Abby Normal 0]

----------------

On 5/14/2003 1:35:24 PM Proper_Bo wrote:

Its like I wasnt even here. Incase you didnt read my last thread......

 

 

SAME SETUP as Abby. This time all GO TO WORK on the same road. Before the sims move, several other cars were seen to take the two roads that the sims seem to chose between.

----------------

"Several other cars..."

See? Proper_Bo is getting the normal traffic automata going to work, as it should be. Just to confirm, Bo, they''re all taking the innermost path (and/or it''s mirror) to work? The two outer paths are pretty much unused?

What are your settings Bo? Traffic on high? Detail on high?

Karybdis: 

"IE someone may be using road a) and road b), however only road b) will show traffic visibly because it has 2 instead of 1 person on it. It likes to do only things that are very noticable visibly. Maybe that''s why you dont see them going there"

 

Unfortunately, that wouldn''t explain why I could see them in previous tests using different maps, and I also see a crapload of them coming home from work. I thought that this may have been the problem which is why I added two more tracks of residential to the end of the road instead of my usual one yard setup.

 

[Proper_Bo 0]

Sorry I wasnt aware that the my sims are a little dodgy for test purposes. Yes got cars (automata) going to work starting at around 5am I believe. Yes they all took the same routes that the sims were taking, the middle road I believe. (yes and it''s mirror)

 

Any further questions? My appologies for not realising that you wanted the normal cars not the sims.

[Abby Normal 0]

No, no problem at all Bo. I didn''t mean to sound so snippy. I just have no idea why mine isn''t working is all. Odd, that. Thanks for the info though!

[Buggi 684]

What about monkey cages? I don''t see an option to place those...

That is EXCELLENT work!! Congrats!

Awesome .NETing dude!

[Abby Normal 0]

I dunno...are monkey cages Impassable or just hard to traverse through...?

 

Hey seven, I''ve started working on that handbook, there is a ton of info but if there is anything you want in there that I may forget, PM me. I''ll show it to you before I hand it off to be posted anywhere.

[Dr_ExK 0]

do you know that ...

 

if you put a sim into a house with a no-job zot, he/she will ''hum hi ho over new job'' in no time? That means, the path finding algo for a sim has no problem, but somehow something else is screwed ? is this observation valid ?

[Sharr 6]

This is a test I made using my latest experimental design.  I recorded it using the "recorder" cheat and put it together using Jasc''s Animation Shop.

 

I didn''t click the *exact* same spot, but you''ll see that the engine only picked the shortest way there one time.

[Abby Normal 0]

What is this recorder cheat? I could really use that for some of my upcoming tests, so as to keep me from having to draw on my screen with a marker.

 

As for the animation, it could use some work but that's a very nifty trick in the first place! What it looks like is when you clicked on the 5th res lot from the bottom the truck went the long way around on top, when you clicked on the 3rd lot it went a more direct way? Maybe you could repeat the test trying to click on the exact same thing? I had previously thought that there wasn't much randomness in the special automata, they tend toward the "straightest path" sort of routes.

[Sharr 6]

literally, the cheat is "recorder". It opens up a little window that will allow you to name the animation and specify the frame rate, and duration of the animation. you can resize the little window that pops up with it to cover the area you want to cover.

Once you are done, you write it out to some folder in My Documents - Recorded Animations. You then need to put the files all together in one gif.

My animation looks clunky because I specified a small frame size, in order to keep the size of the image down. It''s quite small, and does the job. I could make it bigger, if you want a closer look.

[Sharr 6]

Here is a slightly bigger look. The first trip has the truck going to either the 4th or 5th tile from the bottom - it''s on the line. The second trip has the truck going to the third tile from the bottom. I found that odd, since they were really close.

There are several hundred frames here in this animation, and dang if it isn''t rough on my CPU. I wonder if I can get an upgrade for my processor.... it''s an Athlon 1500+ (1.3 ghz).

[Magitek 0]

Heya. I found something interesting today. Unfortunately I haven't had time to catch up on the Travel Time Testing thread. I'm still on the beginning of page 7 or so after some skimming. Anyway, one of the last things I read about, someone was asking people to look out for places where the algorithm might fall into a dead end. I believe I have found just a place!

Ok, in this city, I was trying to separate blocks of zones by only rail. It's not workin' all that well, but that's another story. So, this city has two neighbors which both have road connections to this one. You can see this up in the upper left corner. I was trying to get these connections to hook up to the rail line instead of directly to my zones. I didn't want the people in the zones leaving directly by road. This means I've got at least a little bit of traffic using the rails. (The reason why the road in the corner isn't connected is because if it was, it would be blood red.)

Heading toward the meat of my post.. The important parts of the upcoming scene are the station in the upper left, the station in the upper right, the rail connection in the lower right, and the various railways among said stations and connetion.

http://moogle.sandwich.net/screenshots/sc4_lametrain.jpg
This first shot shows a train happily passing the station in the upper left and driving off to the dead end. It came from the connection at the bottom. At this dead end, I noticed trains disappearing and reappearing traveling the other way. They did not stop at the station. Nobody is using it. They turned around and went to the station in the upper right.

http://moogle.sandwich.net/screenshots/sc4_lametrain2.jpg
I decided to put a loop at that dead end and see if it would swoop around and head back. Sure enough, it did. It should just take the diagonal rail. That'd be the most direct path.

[the7trumpets 10]

thanks for joining us Magitek!!!

 

I'm not entirely sure if the automata really has relevance to how the pathfinding engine is "working" or if it is simply an approxomation of what routes are more used than others.  In any case, this is an interesting find.  Thanks for sharing it.  Did you notice if the automata continued to do this "backtracking" or if it only did it once, and then took the more logical route?  If so, it would support the idea that the automata is more closely tied to the pathfinding engine than originally thought.

[Abby Normal 0]

Hey darkmatter, I manage to dig up a program that seems to be fairly similiar to what yours will be like (except it specializes in the A* algorithm). It might be interesting to take a look at if you want to steal any features for yours. Here is the description:

 

=================================
         F E A T U R E S
=================================

- Draw, load and save maps.
- View the A* tree and open/closed lists.
- Run or Step the A*.
- Breakpoints and 5 break conditions. Set a breakpoint by double-right clicking
  on a point on the map. If that point is queried, the A* will break allowing
  you to examine the tree as well as the open and closed lists.
- Dynamically view the A* search space.
- Create your own heuristic and map extensions to test your pathing algorithms
  before implementing them in a game.

 

Here's the page where it can be downloaded from: A*Explorer

<?A>

[Rendili 0]

Hi everyone,

Have just been reading through most of your experiment post to do with travel times and this thread on pathfinding. You guys have put a lot of amazing work into this, very good stuff.

The reason i managed to find my way over to this corner of the internet is because a) i am a fan of the simcity series and b) am in the middle of writing a java program of my own that attempts its own pathfinding, I have always been interesting in how programs go about doing this.

I have not finished by any meens and I am sure it will never reach the high standards of DarkMatter's program, but it has kept me busy re-learning java again.

Here is the URL

http://www.rendili.pwp.blueyonder.co.uk/pathfinding/pathfinding.html
[edit]changed web space link[/edit]

Feel free to have a play

At the moment the terrain speeds are hardcoded at :

grass 5mph
street 30mph
road 45mph
water 0mph

but plan to in the future to allow the terrain speeds be modified.

Keep up the good work

Paul

[Proper_Bo 0]

I cant see that? Any ideas why? Is the page broken?