[SOURCE] A* Pathing with 3D Viewer

[darrensmith0125]

This C# application when provided with a start and end location allows paths to be calculated through the wow landscape. The path creation can be viewed in wireframe 3D in realtime.

The path generator is PPather which uses an A*ish algorithm. PPather knows about the wow world because it loads up (in chunks) the models and landscape that make up the part of the world you are searching. Starting at the start search spot it adds up to 8 spots around the current spot N,NE,E,SE,S,SW,W,NW, it then determines whether those spots can be reached or are blocked by landscape or models. Spots which can be reached are scored and added to the A* queue. The spot with the lowest score is the one next evaluated by A*, it also gets up to 8 spots around it added which are then scored...The evaluation continues in this manner moving closer to the end point due to the spot/path with the lowest score being evaluated first until eventually the destination is reached. The score is the distance to get to the current spot from the start spot + (the distance to the destination multiplied by a heuristic). Using a larger heuristic makes the shortest path less likely to be found, but the algorithm may path faster.
Pather was written by Pontus Borg around the start of 2008. I wrote the 3D viewer June 2009.
(Link to a good workthrough of A*: A* Pathfinding for Beginners , also see A* search algorithm - Wikipedia, the free encyclopedia)

You could use this application to play with the PPather A* algorithm to see if you can improve it / or just understand it.
This also might inspire you to include PPather in your own bot instead of the waypoint system.

I have included a link to a video (at the end of the post) so you can see what it does without downloading it.

Compilation
To run the application yourself which is probably of most interest to bot developers. Compile it by Downloading:

* Visual Studio C# 2008 (Visual C# 2008 Express Edition)
* Micorsoft XNA Game Studio Express 3.0B (Download details: Microsoft XNA Game Studio 3.0)
* Application link PathTest.zip
(Virustotal. MD5: 1e1045fa564661457758ccb45cca376e)
* You will need the latest version of Wow installed.

if when you load the solution you get "This project type is not supported" then you didn't install XNA.

Usage
Select from and to then click search.
The different algorithms will make a small difference to the path created.
The view window can be navigated using W,A,S,D,X,Space,+,-,Mouse Button Down Drag,Both mouse buttons down


Screenshot


Video link
http://www.youtube.com/v/tKxaTVUnfmI&hl=en&fs=1&

[Dragonshadow]

just link the youtube video link don't put it in tags. auto embedding will do the rest.

[trikinomitry101]

[YT]http://www.youtube.com/watch?v=tKxaTVUnfmI[/YT]

There we go.

Is the auto embedder broken?

[Thelovefool]

+rep from me very nice

[UnknOwned]

without looking i would like to say...
Interesting...

[Dragonshadow]

[yt]http://www.youtube.com/watch?v=tKxaTVUnfmI[/yt]

There we go.

Is the auto embedder broken?

Dummy thats exactly what he did. [YT] TAGS DON'T WORK.

[ame=http://www.youtube.com/watch?v=tKxaTVUnfmI]YouTube - Pather finding a path through Stonetalon Mountains[/ame]

Tur dur.

[Herleybob]

Wow this looks amazing. Ive always wanted to learn this. Will check it out.

[The-Guardian]

Wow... just think of the possibilties this could be used for? very nice, im sure it took a long time to do this.

[ynoorb]

I love ppather lol. I wait with the patience of a sint for some nice bot dev to implement it again since glider has been forced into hibernation . Thanks for bringing it to light for some of those who may not have known of it

[Herleybob]

Seems this cannot run on x64... on x86.

[darrensmith0125]

Seems this cannot run on x64... on x86.

I don't know whether this will work as I run 32 bit XP at home...

Shawn Hargreaves Blog : XNA Framework on 64 bit Windows

How do I fix it?

In your Visual Studio toolbar, there should be a combo box saying 'Any CPU'.

If you are using C# Express, this toolbar entry may be grayed out. To enable it, go to 'Tools / Options', check 'Show all settings', select the 'Projects and Solutions' tab, and check the 'Show advanced build configurations' box.

Pull down the 'Any CPU' toolbar combo, and choose 'Configuration Manager'. Open the 'Active solution platform' combo, choose '<New...>', and create an 'x86' configuration.

[Barnzy]

Wow. Nice, Bot developers will have fun with this

+Rep x2

K this is last post I make for a week as I am now going on holiday. Bai

[Herleybob]

Everything compiles in 'Any CPU', besides PatherPathView... ill continue to look into it.

It wont let me change PatherPathView to x64 or ANY CPU, but everything else i can....

[Aleph]

I always wondered why PPather used the old, pure A* pathfinding algorithm. It's useful when you are giving lectures in pathfinding basics to computer science students (I remeber mine from university), but applying pure A* pathfinding to a huge graph results in an computation nightmare we all know:
PPather standing there, calculating a path to neverneverland or just giving up.
It's actually a well known problem and solutions already exist. Many RTS games optimize pathfinding by using hierachical A* algorithms, where you divide the landscape in bigger "tiles/clusters with entrances", calculating a rough path with these clusters first and then using A* to navigate from one entrance to the next ...

*** hmm can't post images yet ... but google for hierachical pathfinding ***

it's actually the way humans do it ...
if you want to walk all the way from Auberdine to Ratchet ... you don't spend 30 min standing in the Auberdine Tavern precalculating every footstep you will make ...
you actually break down the problem by abstracting the landscape into huge chunks ... knowing their "entrances" ... like the road from Darkshore to Ashenvale ... or the Horde Gate form Ashenvale to Barrens ...
and you use expensive A* only to navigate within these chunks from entrance to entrance ...
small chunks the size of like 50 x 50 yards would be interesting ... entrances would often be "on the roads" ...
another optimization could be ... creating a graph of all roads and/or flightpoints ... fast "long distance planning" could be done with the road/flightpath graph ... expensive A* calculations just to get on and off the road to your final destination ...

[Nesox]

Looks nice, btw im not à pathing expert but if you would remove all non walkable surfaces from the mesh so it would skip those areas when searching it would probablly speed it up alot. Or if you implement an octree instead of an A* alhorithm.
À proper A* algorithm however shouldn't take any longer time than any other pathfinding algorithm if properly implemented.

@OP really nice work, gonna take à look tomorrow when i wake up

@Herlybob lol why do you compile it as release? Compile it as debug instead so can debug it properly and find out why it throws that exception, can't be that hard to fix.