Pathfinding Engine Testing...

[Rendili 0]

Do you get a big grey box?

If so you may need to download and install the latest java 1.1.4 from here :

http://java.sun.com/j2se/1.4.1/download.html

it is about 36mb

I was hoping that it would not require any special downloads.

[Abby Normal 0]

I got a big grey box as well, I was wondering...

I'll give a whirl after this java downloads!

[Proper_Bo 0]

I get the box and it says "load: class pathfinding not found" Which sounds to me like you havent uploaded it or linked it wrong.

 

Let me know how you get on Abby.

[Abby Normal 0]

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

On 5/15/2003 3:24:05 AM Dr_ExK wrote:

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 ?

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

I think the special automata are pretty much completely seperate from the rest of the game. It seems like something they added instead of built in, at least to me. The MySims use a seperate pathing than the rest of the traffic system - I would have thought that it would at least be a more effective system since there would only be at most 5 MySims and I suppose a bunch of firetrucks and police, but apparently it's not. Also, I would guess that MySims can take other sims jobs, but that's just a guess.

[Abby Normal 0]

Okay, I got that pathfinding link to work. You need the Java Runtime Environment which is about 8 megs. I do have a question though:

 

Yellow: Starting point - Red: End point - Grey: Road - Green: Grass

 

How many paths does this thing find?

[Rendili 0]

So far the program does not find the final path (it does have this stored in an array, i just have not got round to displaying it graphically), I will however only look for one path.

At the moment it displays a blue box when it tests a cell to see whether to use it in the path, that box changes to orange when it decides that one of the blue cells being tested is the best out of the blue cells for the shortest route.

What it will do in the future (maybe tonight) is trace the route from finish to start displaying the actual route it chose.

[Rendili 0]

ok,

I have now recompiled the program with a switch that should make it run ok in ie6 without any extra downloads (it works ok on my pc ok, XP IE6). I may work in ealier versions of IE but i do not have a pc with anything older than IE6.

[Proper_Bo 0]

Yes it works without download now  but are you trying to tell me that this is the fastest route? Are you working for Maxis or what?

 

 

Come on.....whats up with it? I counted the squares myself.

 

[DonD13 0]

Keep up the great work guys. I haven't been posting much lately because I just got done with finals, and now I'm going to be working alot more.

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

Sharr wrote:

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).

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

Should be no problem to upgrade to a faster CPU as long as your motherboard will support it (most likely will, you may need to download the latest BIOS though) An Athlon XP2000+ is only like $55 plus shipping these days if you shop around online.

Hope this helps,
Don

[Abby Normal 0]

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

On 5/20/2003 4:43:01 PM Proper_Bo wrote:

Yes it works without download now

 but are you trying to tell me that this is the fastest route? Are you working for Maxis or what?

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

Actually, I would like to know how it came up with this solution as well. What algorithm are you using? Maybe the screwups will be more insightful than the successful shortest paths? Could possibly lead us to the real reason the pathfinding is broken.

[Rendili 0]

I have gone through all the code for calculating the route and one section of it is not doing as i intended.
Basically everytime it queries a cell for the 2nd+ time it resets the cost of travel property of that cell to just the cost of travel for that cell, rather than the cost of that cell plus the cost of all the previous cell to get to that cell. When it goes to calculate which cell has the lowest travel cost it is always going to one that been queried more than once in the direction of the finish cell. this meens that once it sets of on a certain path it doesnt try other paths to see if they are shorter.

I need to go to bed now, only 6 hours till i need to wake of for work, but i will work on this when i get home from work.

[DarkMatter 21]

Wow. You guys already have a working test program. Do you want me to continue working on mine, or will this one suffice?

Abby, so far my pathfinder supports all the features you listed from that other A* Test program, except Breakpoints and dynamically viewing the search space. It is more flexible, though, in that you can plug in any pathfinding algorithm, not just A* ones. You can also define your own types of tiles, and even add custom attributes to them. Its still incomplete, though, and I have yet to write a working A* algorithm. I don't know what I'm doing wrong, but I'm missing something I think. Its hard to find complete information on the algorithm online. Everything is so incomplete, and peoples code is usually pretty horrible.

Anyway, let me know if you guys want me to continue writing my test app. Its pretty feature-loaded now, and I think it would still be useful. I just have to figure out A*.

[DarkMatter 21]

Something else, regarding pathfinding in SC4. After learning what I have about A*, it seems the algorithm is too much for the kind of pathfinding required in SC4. In SimCity, paths are only allowed on transit tiles, not every tile. In contrast, A* searches every tile, all 8 tiles adjacent to the current one. Thats a highly inefficient use of processing power considering the volume of searchable tiles to the total volume of tiles. I've been exploring alternate means of calculating paths, and there seem to be a few ways, one of them is kind of a modified version of A* that has severely limited adjacent tiles, depending on the direction of the transit tile. I spoke about this before on the previous thread, but I've refined my ideas a bit. If I get the chance, I'll post more on it, and if you guys want me to complete my test app, I'll try to write a plugin for this algorithm.

[Abby Normal 0]

I'd love for you to continue on the app you are working on. Especially if it isn't in java, as there is a bit too much lag for my tastes Plus, I think being able to tweak aspects of the pathfinding algorithm or plug in a different algorithm altogether are necessary for the testing aspect of it. If you have any early screenshots of it I'd be glad to give input on the interface or anything really.

 

Also, there's no way to just disallow the diagonals in the calculations? I agree having them in there is a waste for SC4 type usage. Although you may want to keep it as an option.

[Magitek 0]

About my trains. They would take that path repeatedly. Not sure if that makes it more or less helpful. It was kinda random that I found this. I'll let you know if I see anything else odd.

Interesting applet Rendili. As for why it's not finding the shortest path in a case like Proper_Bo's, I think it's just not looking far enough. It sees that there is water to the right and grass everywhere else, so it takes the southern path, because it's closer to the goal. Try putting the start at 3,3, for example, and the end at 10,10. Then put a road to the right from 5,3 to 10,3 to 10,8.. The path will go down and right on the grass because it can't see the road. (.. have you seen my java program Rendili? There's a link to it in my sig. I also have two java applets online. They're not too impressive though. )

[DarkMatter 21]

Abby, scan back through this thread. I posted a screenshot, along with a beta from a few days ago. It lets you test the mapping abilities. If I get the chance, I'll try to post another copy tonight, although its in kind of a broken state. I'm trying to integrate the plugin .dll's into the main program, and its beeing a b*tch.

As for disallowing certain calculations, that depends on the attributes you add to tiles, and your particular algorithm. Tiles in my pathfinder are highly customizable. They all have some static attributes (name, color, weight, cost, passability (passable, nonpassable, and transit)), but each tile can have any number of custom attributes. This would, say, allow you to add a possible_directions attribute, perhapse just a byte value. The 8 bits in this one byte could determine wether its possible for the algorithm to search that direction (bit equals 1), or immediately distregard it (bit equals 0). If a direction is immediately disregarded, none of the adjacent tiles to the tile in that direction will be searched. For a road, this value could be set through a script (scripting is planned, but not yet implemented) when laying the tiles. Depending on the direction you draw the tiles, that custom attribute will be set marking the possible search directions. If you lay a set of tiles horizontally from point a to point b, the script would set that byte to only allow the tiles to the left and right to be searched, restricting all others.

I know thats complicated, but I'll have most of the scary stuff hidden under a nice GUI to keep things easy. The scripted tile laying will allow you to integrate custom tile attributes into the tile-laying process. I'll also allow you to double-click any tile to edit its attributes values (already done, actually, although the tile tracking code has a bug that sometimes makes the highlighted tile fall to the right of the cursor). I'm going to try to make this program as flexible as possible, and also show as much detail as possible so we can dissect algorithms and see exactly what they are doing. I'll try to have as many things scriptable as possible, too, although I don't know how much that will be. It may just be tiles. Anyway, I'll try to fix the major problems with it tonight so I can post another beta. This uses .NET, and while .NET is a bit nicer and faster than Java, its a 20 meg download. I hope thats not too much for everyone.

[Karybdis 34]

Sorry for this being off topic but you guys will probably appreciate this being mentioned.

 

A person who recently went to E3 has confirmed that it appears the pathfinding engine has been fixed in Rush Hour, including highways and other methods.

 

I say appears, but the info certainly looked good to me at the time.

[Rendili 0]

In my program's calculations it does not search or take diagonal moves, it only ever queries a cell immediatly next to the current cell.
Once i have sorted the current problem in the calculations I will add the ability to modify terrain speeds, heuristic multiplyers and maybe the distance a cell covers.
Unfortunatly there is no scope for adding plugins for different algorithms, it is just using A*.
If the grass speed is set to 0mph then you would have to put roads/streets down which would then make it behave more like sc4.

Magitek, i tried to go to your links but got the following error :

Unable to determine IP address from host name for moogle.sandwich.net

[DarkMatter 21]

Ok, here are some screenshots of the latest pathfinder. I've had to remove a lot of the algorithm plugin code, as it was broken somehow. I'll attach an updated beta later on once I get the plugin code working properly, but for now, not much in the way of plugins. Currently, you can edit the map and lay start/destination point pairs. This app will allow you to search multiple start/destination pairs at the same time using the same algorithm. Later on, I'll try to allow you to lay multiple start/destination pairs and select which algorithm is used to calculate the path between them. I'll also try to allow you to lay a single start/dest pair and run multiple algorithms on the same one, allowing you to compare the results.

 

Abby, I'm not sure how easy its going to be to display the data tree. The A* algorithm can be implemented using one of many data structures for the open/closed lists. Some even use the same structure for both lists, simply adding a flag to closed tiles. Other algorithms can store data differently again. With so many possible ways of storing algorithm data, I don't think I'm going to be able to make the tree browser a possability. My last implementation broke the program pretty thouroughly. I have one more idea, but it will make it more complicated to write the algorithms (if the author wishes to have his data displayed). Rather than force a single standard method of storing pathfinding data, I'll just allow each algorithm to edit the contents of the treeview directly. That will take creation of the tree out of my hands and into those of the algorithm developers. It won't be a required feature of algorithms, though, because it won't be easy to visualize the data.

 

 

 

 

[Rendili 0]

DarkMatter that is on excellent looking program!! Certainly puts my feeble efforts to shame...

Anyhow, for those that might be interested, I have re-written almost the entire algorithm coding.
cell speeds are now worked out in kph not mph, and the cell have a default distance of 16m

I have added a graphical representation of the route that it chose, this seems to cut a few corners though.

All the changes seem to have improved things but they are not perfect.
I have uploaded the new version here as the server for my usual webspace seems to have disappeared


[edit]
My web space is now as follows
http://www.rendili.pwp.blueyonder.co.uk/pathfinding/pathfinding.html
[/edit]

I am going to add the ability to be able to change the terrain speeds, cell distance and heuristic multiplyer

I would be interested to know your thoughts on the new version

[Proper_Bo 0]

What a difference a few lines of code can make.

Much Better. Trully.

This is the same test I did an found the faults with, but it worked this time! Well done.

Diagonals! A purple line for the actual course taken! Good work.

 

[Rendili 0]

OK
I think i have the whole program sorted now in terms of accuracy!!

I have added the ability to change the values of the terrain speeds, the grid distance and the heuristic value

boy what a difference the heursistic value can make!!

I urge you all to try the latest version of my program out, it was a true eye opener for me when i saw some of the results after playing with some of the values.

for low speed terrain a high heuristic is needed (around 15) but on higher speed terrains like road and streets a much lower heuristic is needed (around 0.5 which is what i set the default to be)

again, this was an eye opener for me, i highly recommend trying this out so that you pathfinding experts can come to some conclusions about the restults.

My usual web server is back so the link is now back to :

http://www.rendili.pwp.blueyonder.co.uk/pathfinding/pathfinding.html
[edit] my webspace has changed name, please use the above link[/edit]

[Rendili 0]

Thanks Proper_Bo
I used your example to try and fix the code and in my testing on new code.
I still can not figure out why it is taking a diagonal line for the route, it only pathfinds at right angles. It does not seem to take the diagonal on all corners.

[DarkMatter 21]

Great work Rendili. Despite my "beautiful" GUI, you have something over me. I am having a hard time implementing the algorithm itself. I found a book at Barnes & Noble that has several chapters on A*, but its $70, and I can't afford it right now. Any chance I could take a look at your code to see what I'm doing wrong? I would really appreciate it.

Also, this little program is getting bigger and bigger. Its written in C#/.NET, and if your a Java programmer, you could probably pick it up pretty quick. If you would like to help me out with writing algorithms, that would be GREAT! I'd like to have several algs to compare with each other, but the map drawing code needs an overhaul. If you think you could learn C# and write some algorithms that implement an IAlgorithmPlugin interface (I'll send it to you, or better yet, post it on my web site), that would be a big help. I'd like to have some of the base algorithms like Djikstras, depth-first, breadth-first, etc. to compare with A*. Once I figure out my problem with my A* algorithm, I will start writing some altered and hybridized versions of it.

Thanks.

[Abby Normal 0]

Don't worry Dark, the data tree was just a nifty extra on that other one. I wouldn't actually know what I was looking at anyway. I just assumed if the algorithm was being executed in that matter, then it would be a simple thing to just output it to screen (as simple as programming ever is with stuff that seems simple). But you are absolutely right, there are several ways of doing that and I would not bother trying to display it. Indicating the method used would be nice though, so we can compare which methods are better than others in our situation. I love the configurability of your program, looks very promising!

 

Yes, and that first screenshot + beta you posted I completely and totally missed.

 

I can try to find code snippets if you want, although I'm not sure if it will be any more helpful than the stuff you have found.

 

Karybdis: Given they are planning on putting in a feature that lets you see the path being taken to work, I sure hope it is fixed! It would be awfully embarrassing to have that feature in and see what the drivers are doing currnetly! Oh well, we can hope.

 

Rendili: Looking good! You change that thing faster than I can keep up with it. Too bad I downloaded 8 megs of java already I'm very curious to try out the new heuristic feature.

 

Em, I have to work now, crap.

 

[Magitek 0]

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

On 5/21/2003 3:53:26 AM Rendili wrote:

Magitek, i tried to go to your links but got the following error :

Unable to determine IP address from host name for moogle.sandwich.net

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

Hmm, strange. It works for me. You could try going through my old site location: http://www.rose-hulman.edu/~sheridjs

I wish I could help you guys more. I actually have the .NET visual studio on another computer, but I've never used it. Don't know much of anything about C#. I could try and write a plugin for the program if I ever get some time, but as I'm sure I've complained many a-time before, I don't really have time these days. I'll keep watching. If you want an algorithm looked at or code debugged you could try sending it my way. I may be able to help in that respect, but you guys are working on these things so fast that you'd leave me in the dust. Thumbs up to both of ya.

[DarkMatter 21]

Magitek, if you have programming experience in another language, like VB or C++, you could still write a plugin. The beauty of .NET is that its language neutral. I can load any plugin that is written to the .NET managed environment. That could be C#, VB.NET, or C++ using the Managed Extensions for .NET. Hell, you could write a plugin using any .NET compatible language, and that includes just about every language now.

That A* Explorer program Abby posted actually turns out to be the code from this book I want to buy. Its a Game AI book with like 4 or 5 chapters on A*, and there is full source code. This A* Explorer simply uses their code, and wrapps a pretty gui around it. So I think I have enough quality code now to figure out A* (and whatever it is that I'm doing wrong). Once I have a base algorithm, I'll post the code so everyone can see how to write a plugin for my pathfinder. I finally have a chance to breathe now, what with getting a new job, finals, and getting myself set up for the next set of CS courses. Its been a hectic couple of weeks, and I think its finally settleing down enough for me to think.

Abby, if you can find code snippets, that would be great. I'm having a hard time finding any code on A*, just vauge descriptions of how its supposed to work, but rarely enough to figure out the whole algorithm.


Now, on to other things. I've had a question for some time, and its probably been answerd, but I'll ask anyway. Do all the sims in a single building work at the same place? I mean, I can see that happening with a small stage-1 house and an industrial workplace. But what about some of the larger buildings that house thousands of $$$ sims? Do they all work at the same building, or do say all 3500 sims work at different places? Reason I ask is that for any given starting point, if all the sims work at different places, which seems like a very plausible thing, there could be 3500 paths from one building to 3500 workplaces. How exactly do you show the path from home to work for all 3500 sims? When this building gets a no-job zot, does that mean that all 3500 sims are out of work, or just one? Is this one sim not working because traffic is too bad, because there is no work in the current map, and if this one sim can't find a job, does the entire building vacate because of a pathfinding issue? Just a few questions I've been pondering for a while. The thing that brought it up was an RC city I had that had several huge hirises, but was mostly CS$$$ jobs. Buildings like Ong Condos and Byall Towers house thousands of sims, but few of the available jobs employed that many. Seems that the sims from these larger res buildings would each have to find different routes to work, because work could be different for them all.

[Rendili 0]

Magitek, the link worked today, I am at work at moment and do not have the java runtime on my pc here, but I will download it when i get home. From what the screenshots show, it looks very impressive.

DarkMatter, I would be happy to email the code to you if you are still interested, just let me know what your email address is.
If I can help some areas let me know, I wouldnt mind trying to pick up another language.
I have no idea how to go about programming in C#/.NET, or what application you need to compile and write. The reason i chose Java was because the compiler and composer are free downloads. Can you download all you need to write and compile in C#/.NET for free?

I was playing with those heuristic values on my program this morning and it makes a huge difference to the accuracy and processing time. The higher the value the quicker it is taking less processing to find the finish but it less accurate, the lower the value and it can take much longer depending on how many possible routes there are, but it is much more accurate.

[DarkMatter 21]

Rendili, you can download all the tools you need to program with .NET. Check www.microsoft.com/net. You will need the runtime and the SDK, the SDK beeing what contains the compliers and such. They are fairly large all together.

C# is similar to Java, but closer to C++. It still allows the use of pointers and references, and it's syntax is closer to C++. But, if you know either Java or C++, you should be able to pick it up very quick. In .NET, there are namespaces rather than packages. All the namespeces in the .NET Framework start with System. For example, IO classes are System.IO, and all Windows forms classes are System.Windows.Forms (equates to the AWT or Swing classes).

I think this project would be more fun if a couple people were working on the algorithms. We could collaborate and figure out better ways of doing things. Magitek, your welcome as well. The more minds the better the algorithm.

[the7trumpets 10]

First things first, I'm sorry I've been scarce this last week, my power supply went kaput a few days ago and I've been working like a mug since Monday.  You guys have made so much progress, I hardly know what to say!  Let's keep it up!!!

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

On 5/22/2003 12:12:53 AM DarkMatter wrote:

Now, on to other things. I've had a question for some time, and its probably been answerd, but I'll ask anyway. Do all the sims in a single building work at the same place? I mean, I can see that happening with a small stage-1 house and an industrial workplace. But what about some of the larger buildings that house thousands of $$$ sims? Do they all work at the same building, or do say all 3500 sims work at different places? Reason I ask is that for any given starting point, if all the sims work at different places, which seems like a very plausible thing, there could be 3500 paths from one building to 3500 workplaces. How exactly do you show the path from home to work for all 3500 sims? When this building gets a no-job zot, does that mean that all 3500 sims are out of work, or just one? Is this one sim not working because traffic is too bad, because there is no work in the current map, and if this one sim can't find a job, does the entire building vacate because of a pathfinding issue? Just a few questions I've been pondering for a while. The thing that brought it up was an RC city I had that had several huge hirises, but was mostly CS$$$ jobs. Buildings like Ong Condos and Byall Towers house thousands of sims, but few of the available jobs employed that many. Seems that the sims from these larger res buildings would each have to find different routes to work, because work could be different for them all.

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

Well, I believe I have the answer for you, but I have to include a disclaimer that it has not yet been fully tested, so I cannot claim absolute truth of this.  However, I feel fairly certain that it is correct:

Sims in ANY residence all start out traveling to the nearest workplace (by air distance).  If they get to a workplace before they get to the intended destination, they unload as many sims that can work there.  If there are still some sims left in the "carpool" they continue from there and rerun the pathfinding algorithm again to find the nearest job to where they are currently.

For example, 150 R$$ sims leave a nice apartment complex.  They travel to the nearest workplace, which is a Co$$ building, which can employ 125 R$$ sims.  25 of these jobs are already taken, so the carpool unloads 100 sims at this job, and the 50 remaining R$$ sims rerun the pathfinding algorithm.  The closest job site for R$$ from the Co$$ building is a Cs$$ building.  The 50 sims make it to that job, and since there are enough jobs for them in that building, they all work there.

 

Reasons for me thinking this is the way it works:

1. Mass transit buildings of one type when next to a high-rise are frequently overused with no usage in an identical building one tile further from the high rise.  This suggests that ALL the sims in that high rise are using this particular station because the beginning of thier commutes are identical.
2. To limit processor usage.  If the heuristic was restricted so much that routes are terrible, you know that maxis had trouble with too much processor usage.  Computing the pathfinding algorithm for each 'residence' instead of each person cuts down on that dramatically.
3. Game lag seems to stop getting worse after a few hundred thousand sims.  This suggests that after a certain point, the number of calculations done for the simulation is negligable as the number of sims in each lot increases.  The only explination for this is that the calculations made for sims are based more on per lot than per sim.

So,  I hope all that makes sense.

 

OOOOOOOOOOOH!!!!!!!!!!!!

I just had a thought!!!  I think since the pathfinding engine 'stops' at a job if it sees one on the way to its destination (claimed by maxis) means that it is impossible for the pathfinding engine to be a vertex based A* algorithm.  In order for it to be able to 'check' whether there is a workplace it is passing, it has to stop at EVERY tile to check.  In a vertex (intersection) based A*, this would only happen at intersections.  So, using this algorithm (which looks very promising to me) would prohibit 'checking' to see if the sim is passing a possible job on the way.  There are ways around this, but I would be surprised if it is so.  For instance, each length of road between two vertices could not only have a transit time value, but also a 'jobs available' value.  But, this would require updating the road map for the pathfinding algorithm every time a C or I plot developed into something different, which would be very resource costly.