Pathfinding using A* algorithm

squisher · Post by **squisher** » Mon Jun 23, 2008 3:19 pm

http://a-star-algorithm-implementation. ... tation.zip

Now I just gotta figure out how to apply this to 3d space

SG57 · Post by **SG57** » Tue Jun 24, 2008 12:13 am

I haven't taken a look at that archive, however just think of 3d space as a 3-dimensional array when it comes to the 'map'. Basically all searching and checking and calculating done also gets done in 18 more 'squares' where in 2d it's 9 (well maximum anyways).

Just think of a cube 10x10x10 element array filled with '0's and ' 's and other symbols meaning a walkable space is there or a wall or etc. Then apply the same logic and math and whatnot as used in a 2d A* version, just take into account the new direction of movement (in and out) and the new diagonals.

Darktib · Post by **Darktib** » Tue Jun 24, 2008 5:10 pm

For matricial A* pathfinders : In 2d you can look up for at most 8 cell from a specific cell, whereas in 3d you look up for at most 26 cells...

There is a serious performances hit when ou create a 3d Astar pathfinder...

As SG57 says, for a 3d pathfinder you need to create a 3d array for the pathmap

Zeuss · Post by **Zeuss** » Wed Jun 25, 2008 1:33 am

Depends on what you mean by 3d space.

If it is for a space sim, you could probably just get away going in a straight line to the target, and steering around the anything that is in the way.

There are a few ways way to steer around an object might work like this:

Cast a ray from your position to the target
Does it intersect with an object.
Get the centre of the triangle that ray intersects with
Push that centre out by the triangles normal by about 25% of how wide the object is
Get a perpendicular vector to the normal
Travel along that vector for %25 of the objects width
Goto step 1

You could also take a look at opensteer

That has demonstrations of techniques for avoiding obstacles in 3d like space and still getting to the target.

A* in true 3D is too impractical

MasterGod · Post by **MasterGod** » Thu Jun 26, 2008 8:26 pm

Maybe you can create some 2D image out of your 3D scene and navigate through that?

Darktib · Post by **Darktib** » Fri Jun 27, 2008 4:05 pm

@MasterGod : this will not work correctly because of 3D. You will find false paths if you use this method...

The only solution for A* in 3D is to use anon-matricial pathfinder (also known as a pathfinder with a sparse matrix)

bibiteinfo · Post by **bibiteinfo** » Tue Jul 01, 2008 4:22 pm

For 3D pathfinding you can check this :

http://sourceforge.net/projects/argorha/

Right now I'm checking to make an Illricht implementation

Darktib · Post by **Darktib** » Sat Jul 05, 2008 7:25 pm

Interessant screen on sourceforge... but i cannot start the editor because the 'OgreCore.zip" file is missing...

Nadro · Post by **Nadro** » Sat Jul 05, 2008 9:32 pm

This project also looks very interesting: http://sourceforge.net/projects/twang/
This is pre-alpha version and has got many bugs, but looks fine:)

bibiteinfo · Post by **bibiteinfo** » Mon Jul 07, 2008 4:35 pm

You need to download the media package and extract it into the same package as the bin_zip. I'm trying to change engine because of this, too hard to use. I cannot put both package into a unique one because of space issues with source forge.

To use the demo, make sure to read http://argorha.wiki.sourceforge.net/How+to+use

Darktib · Post by **Darktib** » Tue Jul 08, 2008 3:20 pm

I remember that i have downloaded Ogre 6 months ago, so i will test when i will have found the directory of Ogre...