I f anyone has implemented A* pathfinding

[Crirus]

Hello!
If anyone has implemented A*, I whould like to hear some advices how to make
it as fast as possible....
I use ArrayList to store nodes, there is a faster class for store nodes
Point and where I can search for particular one?

 

[Dmitriy Lapshin [C# / .NET MVP]]

Hello,

It actually depends on operations you perform on the nodes. If you need to
remove nodes from the middle of the list, I'd suggest some kind of linked
list instead. Not sure the Framework has one, but it is pretty simple to be
implemented. If you just accumulate nodes, ArrayList seems to be fine, but
you should predict at least approximately the final number of nodes to avoid
unnecessary memory allocations.

P.S. There's a dedicated newsgroup where .NET performance questions are
discussed (microsoft.public.dotnet.framework.performance). Not that I am
trying to be a kind of "policeman" here, it's just I believe you'll get more
expert answers in that NG.

 

[Herfried K. Wagner [MVP]]

If anyone has implemented A*, I whould like to hear some advices how to make
it as fast as possible....
I use ArrayList to store nodes, there is a faster class for store nodes
Point and where I can search for particular one?

You will find a solution written in C# here:

<http://www.codeproject.com/csharp/graphs_astar.asp>

 

[Crirus]

Have any advice about heuristic in a square grid?

--
Ceers,
Crirus

------------------------------
If work were a good thing, the boss would take it all from you

------------------------------

Hello,

It actually depends on operations you perform on the nodes. If you need to
remove nodes from the middle of the list, I'd suggest some kind of linked
list instead. Not sure the Framework has one, but it is pretty simple to be
implemented. If you just accumulate nodes, ArrayList seems to be fine, but
you should predict at least approximately the final number of nodes to avoid
unnecessary memory allocations.

P.S. There's a dedicated newsgroup where .NET performance questions are
discussed (microsoft.public.dotnet.framework.performance). Not that I am
trying to be a kind of "policeman" here, it's just I believe you'll get more
expert answers in that NG.

--
Dmitriy Lapshin [C# / .NET MVP]
X-Unity Test Studio
http://x-unity.miik.com.ua/teststudio.aspx
Bring the power of unit testing to VS .NET IDE

Hello!
If anyone has implemented A*, I whould like to hear some advices how to make
it as fast as possible....
I use ArrayList to store nodes, there is a faster class for store nodes
Point and where I can search for particular one?

 

[Jay B. Harlow [MVP - Outlook]]

Crirus,
Not sure if the following addresses performance or if it just discusses the
algorithm.

http://www.policyalmanac.org/games/aStarTutorial.htm

Its been too long since I read it ;-)

Hope this helps
Jay