[Arianne-devel] A* problem and solution

[Miguel A. B. L. <mig...@ho...>]

Hi,

Actually A* is giving some problems because searchs takes too much time.
Our actual fix is to limit the distance we will search a path, so number of 
nodes is limited, unfortunately this way of working doesn't fix the problem 
for long path searchs.

My proposal is to use a navigation layer:
http://stendhal.game-server.cc/navigationpoints.png
( Big image )

The blue point define the points where A* will be applied, so to seach a 
path from top-left blue point to bottom right blue point we will only need 
to seach in 36 nodes instead of 4096 nodes. As you see the simplification of 
the map is awesome.
The only requirement is that each navigation point has at least a neighbour 
on the same row or on the same colum.

In other to do a good path searching we will have to do:
0) Route={}
1) start=search nearest blue point to start point
2) Route=Route+search(start point, start)
3) end=search nearest blue point to end point
4) Route=Route+searchNavigationMap(start, end)
5) Route=Route+searchNavigationMap(end, end point)

return Route

The only drawback that this method has is the creation of roadways ( 
pathways ) that all A* users will follow...

If someone wants to implement this system... :)
A* algo is done, you would only need to define the data structure to host 
the navigation map in such a way that it is efficient.

Regards,
Miguel