New Pathfinder - Aystar Replacement

[Felicitus]

Hi,

I started two days ago working on my FelicitusAI, which aims to compete with the "professionals" playing on Kurt's Goal Servers (I consider myself being also one of those junkies hanging out there A LOT ). FelicitusAI mainly uses trains - so I started some basic things, like building a railroad track between two coordinates. Since a good starting track is the essential thing of winning a game on Kurt's server, I first started with the Aystar pathfinder. Unfortunately, it takes several months for it to calculate the path for a distance of around 80-100 squares - which is not acceptable for a hard-to-beat AI.

So I did A LOT of research, but I didn't find an algorithm which is fast enough to calculate a path for a distance of 80-100 squares in an acceptable amount of time (acceptable would be <1 month, better 10 or 15 days). I think it is because Aystar tries to find a "perfect" route, but perfection isn't the key on the first line. So I'm trying to implement a pathfinder for rails which uses a different concept.

1.) Basic Pathfinding

The pathfinder connects the start and end point using an imaginary line. Then it follows that line, and if some barriers are in the way (like factories, towns, etc), it splits the line (=creating segments), moving the split point out of the way (which means that the point will be moved in west/east or south/north direction, based on a random value) and starts from the beginning. It does that until a path without barriers is found.

2.) Path Cost

The pathfinder can be configured, so that you can specify different "costs" (not the real game money costs, but also costs like climbing hills for the trains). The costs are stored per-segment.

3.) Segment Rating

Each segment gets a rating, based on the path cost. The totals of the ratings are stored in the path.

4.) Multiple iterations

After the path has been built, the AI engine could run the pathfinder multiple times to find a better path. This is a big difference in the concept of Aystar. Aystar can also iterate multiple times, but it doesn't return a valid path unless endless iterations are given. This pathfinder should return a valid route each time it is called, except if there isn't a valid route available.


Because I'm not sure if my concept will work, are there any alternatives (like the B*-Tree?) to try out?

With best regards
Timo / Felicitus

[Zutty]

I don't wish to discourage you, but perhaps you should not try not to reinvent the wheel. In the very least do some research before starting from scratch. Almost certainly someone else in the world has attempted this before you. These pages seems to have some interesting links...

http://www.gameai.com/pathfinding.html
http://www.red3d.com/breese/navigation.html

I'd strongly encourage you to read all you can.

If all you want though is a faster pathfinder, why not try a different heuristic. The A* heuristic (I'm referring to the whole f = g+h thing) is admissible, that is that it never overestimates the cost (the distance, in general) towards the goal, and is also optimal (assuming its consistent). This means that you wont get any faster than A* without using an inadmissible heuristic, meaning you would no longer be guaranteed the lowest cost path. An inadmissible heuristic (e.g. if you drop the g term) will probably create some crazy paths, but it could be made to run pretty fast. I'm not sure how much faster it would be than the library pathfinder, but its worth a try.

As a starting point I'd suggest you play around with the _Cost() method in the library pathfinder.

Good luck.

[Yexo]

I don't wish to discourage you, but perhaps you should not try not to reinvent the wheel. In the very least do some research before starting from scratch. Almost certainly someone else in the world has attempted this before you. These pages seems to have some interesting links...

http://www.gameai.com/pathfinding.html
http://www.red3d.com/breese/navigation.html

I'd strongly encourage you to read all you can.

If all you want though is a faster pathfinder, why not try a different heuristic. The A* heuristic (I'm referring to the whole f = g+h thing) is admissible, that is that it never overestimates the cost (the distance, in general) towards the goal, and is also optimal (assuming its consistent). This means that you wont get any faster than A* without using an inadmissible heuristic, meaning you would no longer be guaranteed the lowest cost path. An inadmissible heuristic (e.g. if you drop the g term) will probably create some crazy paths, but it could be made to run pretty fast. I'm not sure how much faster it would be than the library pathfinder, but its worth a try.

As a starting point I'd suggest you play around with the _Cost() method in the library pathfinder.

Good luck.

It's not the _Cost() function you should play with, but the _Estimate() function. Try to multiply the return value with 0.9 and wee what results that gives. If you do so, the path is no longer optimal, but it's calculated faster.

[Felicitus]

Okay, I had a look at different algorithms using the Pathfinder2D application and from all these algorithms, A* performs best in most cases. So I tried to follow your suggestion to play around with _Cost and _Estimate, however, it seems that I'm unable to use a non-downloaded library.

Basically, I downloaded the libraries using the "Online Content" function, and decompressed the .tar files, but OpenTTD doesn't seem to recognize the libraries, neither in the content_download directory when not compressed, nor in the path where I keep my own AI (which loads perfectly).

So where should I place the libraries, and is there a way to get the libraries out of SVN?

cheers,
Felicitus

[Yexo]

Okay, I had a look at different algorithms using the Pathfinder2D application and from all these algorithms, A* performs best in most cases. So I tried to follow your suggestion to play around with _Cost and _Estimate, however, it seems that I'm unable to use a non-downloaded library.

Basically, I downloaded the libraries using the "Online Content" function, and decompressed the .tar files, but OpenTTD doesn't seem to recognize the libraries, neither in the content_download directory when not compressed, nor in the path where I keep my own AI (which loads perfectly).

So where should I place the libraries, and is there a way to get the libraries out of SVN?

cheers,
Felicitus

The libraries should be in "ai/libraries/<category>/<libname>/". Take for example AyStar, then <category> is "Graph", and <libname> = "AyStar", (or "AyStar.4", whatever suits you).

You can't get them from svn, as they are no longer in the official repros.

[Felicitus]

Ah - that's it - the category was missing Seems that the directory parser is very strict about the hierarchy there.

[Felicitus]

Okay, that's impressive - I multiplied the costs with 1.1 and it took only 82 ticks to complete (instead of >1000 ticks without multiplication). If multiplied by 0.9, it takes nearly the double amount to calculate. The manhattan distance was roughly 80 squares, I'll try that thing with longer paths now. Thanks for the pointer!

If everything works well, would it be possible to add a multiplicator to the Rail Pathfinder, so that I can use the pathfinder without the need to deliver a modified version of it?

cheers,
Felicitus

[Hephi]

Ok so in an attempt to speed up the annoyingly slow railpathfinder I tried what is talked about in this thread.

Code: Select all

	function MyRailPF::_Estimate(cur_tile, cur_direction, goal_tiles, self)
	{
	   local est = ::RailPathFinder._Estimate(cur_tile, cur_direction, goal_tiles, self);
	   return abs(est * 1.3);
	}
//	function MyRailPF::_Cost(path, new_tile, new_direction, self)
//	{
//	   local cost = ::RoadPathFinder._Cost(path, new_tile, new_direction, self);
//	   return abs(cost * 1.1);
//	}

The estimates need to be made higher (not lower as mentioned above) to speed up the proces.
If I try manipulating the costs the railpathfinder just crashes so that's not gonna work.
This is very very cool!