27-08-2002 05:11									#1
	Flaw in pathfinding Avatar Enlargement: We've got the solution

I was playing earlier today, and noticed a bit of a flaw in the pathfinding in v1.29f and was wondering if anyone else has run across it themselves.

At that point in the game, I had already gotten steam power, and have railroaded the majority of the pertainent section of the continent the pieces were on, but there were still a couple of gaps between cities with just roads.

I had several workers I wanted to move from the region of one city to the area of another maybe 30 squares away. When I went to move the workers to the square I wanted them on, it said it would take 2 moves, but if I moved them to an adjacent square using the 'g' command, then manually moved them to the right square, I was able to do it in 1 move.

Zooming out to get a better look at the pathfinding, I found the following was happening. The majority of the move was left to right across the board, with only a couple of squares of south-to north really needed. However, two of the aforementioned non-railroad gaps were in the middle of the interviening squares. The northern one of the two gaps was through forest and had 3 squares with just road. The southern gap had one square of just road left (and was being railroaded at that time). That was the only section of the area where the units would actually have to go on roads until they got where I wanted them.

If I wanted to move the workers directly to the square I was moving to, the pathfiinder would take the northern route. Move down one square, and they would take the faster southern route. It appeared as though the bias to finding the route requiring the least number of movement points was not outweighing the bias to finding the path moving through the least number of squares heavily enough, such that it was failing to check that southern route once my destination was far enough north of a certain chokepoint that they had to move through anyway.

If this doesn't quite make sense to someone, or people want to see exactly what I mean, I could zip up a copy of the save-game and post it. May need a little help though. I'd modded in a couple of extra buildings, and am not completely sure what I might need to include with a savegame of a mod.

	27-08-2002 12:08									#2
	Got spare money?

I have seen this happening, too. The game is apparently not 100% successful in finding the best path when there is a mixed railroad-road-nothing route needed.

	27-08-2002 15:20									#3
	Support Apolyton, buy Alpha Centauri

There are a number of path finding errors, even if they are relatively speaking small. Most of these occur when you have 2 distinct long paths, where at a certain point the wrong of the two is chosen, even if it leads to a longer path...

Another path finding problem is that if a unit will do multiple turns over a move, he sometimes doesn't end his move in territory with a road, making leaving the tile a problem. For instance a mountain that is in the middle of a path can be taken, but if you leave the mountain, you lose another movement. If there is a road around the mountain in 4 tiles, most of the times it would be better to take the road... the AI doesn't always do this.

Overall, the path finding is solid, but I could improve slightly. As the most problems happen with long paths, I can only guess that it was a reduction of cpu time that limits the perfectness of the path finding...

DeepO

	27-08-2002 17:04									#4
	Put an end to popups!

Just remember the pathfinder in Civ2 and thank the gods(programmers) that managed to improve it.