Pathfinding Engine Testing...

[Rendili 0]

DarkMatter, I have downloaded a .NET setup, about 106mb, does that sound about the right size?
If this sounds like the correct download I will install Monday evening or Tuesday as I am away in Paris this weekend.

Just wondering whether interest has disappeared for the pathfinding testing, it has gone all quite recently.

Anyhow, I have updated my little java pathfinding program a bit (got stuck on an area), it now shows journey time and calculations made to find the path. It also shows the distance traveled some times, I am having trouble getting the text box refreshed all the time, for some strange reason it seems to be linked to when it takes a diagonal path when it displayes the route taken

I also tried to get it so that you can create a road layout by importing a jpg of a screenshot from SC4, but gave up when I was unable to rotate the image to align with the grid on the pathfinding program. I only have the image tools that came with WinXP and Office2000.

http://www.rendili.pwp.blueyonder.co.uk/pathfinding/pathfinding.html

[Magitek 0]

Rendilli, it would be easier to try and load in a shot of the traffic data map or the zones map than an actual screenshot of the roads. (Not sure if that's what you were trying to do or not.)

DarkMatter, in a week I will have access to my AI textbook again. I can look through it a bit and see if there are any interesting pathfinding algorithms. Let us know what inputs and outputs a plugin needs to have when you get that part working.

[DarkMatter 21]

Ok all. I've figured out A*, for the most part. I now have a working algorithm plugin, and some preliminary code to draw the found path. Currently only works on the first set of start/destination points layed down, all others are ignored for now. It also only runs completely, no single stepping yet. I'm having a hard time getting tile costs to work, but it may just be that I'm not adjusting the cost enough. Either way, adding tiles with a higher cost will eventually cause the algorithm to be disuaded from including them in the final path. Tiles will also have a weight, so for things like road vs. street, you could give them the same cost, but adjust their weight to determine which is chosen.

 

 

Magitek and Rendili, I've designed an interface that includes all the methods, properties, and events that an algorithm should implement to integrate properly with the client program. Implementing this interface in your class will allow me to find it, load it, and use it properly. Here is the interface, and as soon as I get the chance, I'll upload all my code to my web server. But this should get you started. Rendili, 106 sounds about right. One thing I didn't tell you is that you need the .NET Framework version 1.0. The new version, 1.1, is out now. I havn't downloaded 1.1 myself, so I can't guarantee that this program will work with it. It SHOULD work, but I don't know for sure.

For everyone, I've attached the latest beta of the pathfinder. I need some testing on tile costs that actually cause the algorithm to be disuaded from using them in favor of less costly tiles.

 

There are some things that I know need to be implemented, and I have plans to make them a reality. One of them is a configuration dialog for algorithms, so we can set the heuristic adjuster and configure other settings for the algorithm. I also want to allow more controls for viewing paths, the open/closed lists, etc. Tile lists arn't yet savable, but a whole entire tile pallette editor is planned. This will allow you to automatically add any tiles in the map that are not on your pallette, update tiles in the map that have the same name as those in the pallette, etc.

 

I did run accross a strange problem, and I don't know why it happens. Whenever you place the starting point in a partially closed area, the algorithm freaks out. My heuristic is currently calculated as the manhatten distance from the tile beeing tested to the destination times a heuristic adjuster set to 1.0: (abs(d.x-t.x) + abs(d.y-t.y))*heuristic. Here is a screenshot: 

 

 

 

Any insight as to what would cause this is greatly appreciated.

 

Well, thats about all for now. The new beta is attached, so download and play with it and have fun. Its still a long way from finished and particularly useful to us, but its a start. What we have to do now is figure out how to tweak this algorithm or write new ones that simulate SC4's method more closely. Something were also going to have to do to get accurate testing is add a traffic simulator to simulate traffic along the calculated paths. Eventually it would probably be useful to add congestion calculations, multiple kinds of transit (not tiles, but things like mass transit, with their own weights), the ability for a path to change transit modes midway, etc. Well, enough talking. Its 2am and I need to get some sleep.

[rezi 0]

There are three type ways middle is default, left is adding roads, right is left's fastest way.

 

 

 

and it's commute time left and right are same.

 

 

 

 

 

 

 

 

but in left way,my Sim dont take fastest way

So,I could guess my Sim doesnt show real(?) commute way.

they take fasteret way at upwarding

but, at downwarding, they take this way. 

 

 

 

 

After getting more bigger building use traffic simulater(

 

 

[Dr_ExK 0]

rezi,

 

it's a nice experiment . However, I think it's difficult for outsiders to rationalise the path finding algorithm if it has a programming bug, like having a '+' where you're supposed to have a '-', or using '=' instead of '==' in an 'if' statement, etc. Whatever conclusion we try to draw would be flawed, if the rationale simply didn't exist in the first place. I feel that there are still plenty of programming bugs in the code.

 

 

[Edman_123 11]

I have a question. Could I extract the patfinder into a folder in plugins, or does it need to be the plugins folder?

[dmrsunz 2]

Abby,

How do you know the commute time was 21 minutes (as stated in post 3 of this thread)?

[Abby Normal 0]

Hi dmrsunz!
Well, I know the commute time is 21 minutes from the commute time graph. And if you're thinking "Well, how does he know which path they took?", that's a good question. The answer is, it doesn't matter - because every path is equidistant from the destination. I was hoping that by seeing which path they took when there was no incentive for any one in particular. Some pathfinding algorithms wouldn't like the backtracking of the inside path, some would tend to shoot as far toward the destination as possible before being forced to change route, etc. I don't remember the outcome though, it's been a while. I really wanted to try something similiar to rezi's stuff (which is an excellent, excellent idea, btw), but life happened and I got sidetracked. Along with technical difficulties, as well. Glad to see some people are still finding these threads interesting!

[phungus420 0]

I posted this already in the Walking abandonment thread, but it does relate to pathfinding, and if maxis fixes this it's crucial to everybody, not just those interestead in the specific walking abandonment thread:

Maxis has made an official reply to the walking abandonment bug. They are asking for us to upload cities where this has an obvious effect to simcityscape. Below is the reply and link:

Author: MaxisFrank
Date: Sep-02-03 02:42 PM PDT
Subject: Re: Something Maxis Should Read

Ralphael (or any others that can help out here),
Any chance of getting someone to post one of these problem cities to SimCityScape and give me a clue where it is there? I'd like to tweak the exemplars on our end and understand what you all are seeing in this city.

Also, I see reference to tweaking one exemplar with one value. If the walking speed is being tweaked, did you tweak all the walking values in this parameter? There should be at least two (one for roads & one for streets).

Thanx,

MaxisFrank


Link: http://simcity.ea.com/bbs/messages.php?&bbsID=61&openItemID=item.261&threadID=0f9d1749cdef413a65f10da4ebbd5044&directoryID=261&startRow=101

[DaveParker 0]

I'm posting this here as it's the only pathfinding topic I can find that's not been locked, so I'm assuming this is the right place.
Weird path screenshot
At point A I have a MySim who says she works at the high school at nearby point B but complains about living in the bermuda triangle. When I query the house the commute shows long. When I use the route query tool she isn't even going to the high school at all! Instead, she's travelling to the neighbor city to the east - and going a really weird way.
She travels down to point C which is an avenue going over a ground highway. She then mysteriously drives off the bridge and onto the highway (despite there being no onramp there) and travels towards point E at which point she turns around and heads back the other way. Why can't she turn at point D (southbound 1-way street)? She then goes all the way east on the avenue/highway and leaves the city.
I get the same path both with or without the new RH perfect pathfinding mod installed (the perfect pathfinding mod did fix a problem I was having with freight trucks travelling miles away to get to a freight station despite having a nearby road neighbor connection though). I've left it several months and the path hasn't changed.

[DonD13 0]

That is some strange pathfinding there DaveParker. I've seen lots of different oddities with pathfinding in RH, varying from pretty realistic to downright rediculus. I especially noticed that in a neigboring city (mostly res, with some light density com) the commute time graph oscillated between 120 and 140 minutes every couple of months. Sadly I deleted that city without thinking to snap a few screenshots. I hope 7trumpets et.al. can help fix this once again

PS: are you the same Dave Parker who posts on the LAB?

Later,
Don

[DaveParker 0]

Since I'm not sure what LAB is I think that's someone else. But that one screenshot highlights a few problems. I don't think these are new to Rush Hour, but the new route query tool certainly helps to spot what's going wrong.

First, from what I can tell, the house that a MySim lives in, has a different place of work to the MySim (when route queried the path goes to a different place of work to where the MySim says they work). When a MySim complains about a long commute they appear to be referring to this 2nd commute (the path shown by route query, rather than the path to where the MySim claims to work).

Second, sims are able to enter / leave highways even when there are no onramps.

Third, not sure about this, but there may be a problem with MySims turning around on avenues when intersected by a one-way street.

Another bug, not related but it's annoying me so think I'll mention it quickly here: toll booths continue to bring in money even after being destroyed. I have no toll booths in my city but get several thousand $ each month from tolls.

[Sharr 6]

I hate to close this thread but there is a Rush Hour Commute thread that is dedicated to pathfinding. Please put all tests and responses in that thread.

[thomasdebruyne 0]

i have a question every body know the testing cheat in sims 2 .

there have a testing cheat in simcity 4 ?

[TinySim 4]

For christs sake DO NOT POST IN A 3 YEAR OLD THREAD!