From: Miguel Angel Blanch Lardin <miguelangelblanchlardin@ho...> - 2005-06-07 15:02:05
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:
( 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:
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)
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.