A* Path Finding

[Shard]

Hey guys, I'v started working on A* and I'm wondering how Leadwerks does it/implements it.

 

Currently I'm creating a "grid" of nodes that contain x-y coordinates and 8 pointers to other nodes around it (n,s,e,w, etc) , where I will parse in the scene to detect objects and then mark off the location of the objects in the grid as impassable. The currently problem that I'm running into is that this leads to the grip taking up a very large chunk of memory (a 512x512 map would take up 10 Megabytes of memory) and isn't efficient for 3D maps at all (like indoors maps). Plus I'm not sure how to detect the slope of the terrain to determine if a character controller can climb up it or not.

 

How have you guys implemented your A* maps?

 

MapGrid.h

#pragma once

enum aStar{blocked,clear};

struct Node
{
aStar value;

Node *n;
Node *s;
Node *e;
Node *w;

Node *ne;
Node *se;

Node *nw;
Node *sw;
};

class Map
{
public:
Node **grid;
int sizeX;
int sizeY;

Map();
Map(int,int);

};

 

 

MapGrid.cpp

#include "MapGrid.h"
#include "Windows.h"

Map::Map()
{
//Woo I'm a default constructor. 
}

Map::Map(int sizeX, int sizeY)
{
this->sizeX = sizeX;
this->sizeY = sizeY;

this->grid = new Node* [sizeX];

for(int i=0;i<sizeX;i++)
{
	grid[i] = new Node[sizeY];
}

//Making each node point to all the nodes around it
for(int i = 0; i < sizeX; i++)
{
	for( int j = 0; i < sizeY; j++)
	{
		if(i == 0)
		{
			grid[i][j].w = NULL;

			if(j == 0)
			{
				grid[i][j].n = NULL;
			}

			else if(j == sizeY-1)
			{
				grid[i][j].s = NULL;
			}
		}

		else if(i == sizeX - 1)
		{
			grid[i][j].e = NULL;

			if(j == 0)
			{
				grid[i][j].n = NULL;
			}

			else if(j == sizeY-1)
			{
				grid[i][j].s = NULL;
			}
		}
	}
}
}

[Niosop]

LeadWerks doesn't do it, you'll have to implement it yourself. I've implemented a similar system to what your doing in Lua, but it's really inefficient. For a faster and more efficient system you should look at the recast integration that Chris was doing, or look at MicroPather which is a more generic A* solver.

[Pixel Perfect]

If you want fast A* you shouldn't be using oop at all, it will just slow it down to much and take much more memory. Confine your use of OOP to higher levels. No one uses it in anything that really requires high performance. No need to store x, y co-ordinates etc because they are easy to calculate on the fly by virtue of the grid poisition. A simple byte array is really all that's needed to either store a 1 or a 0. The memory foot print would then be about 250K.

 

Take a look at Patrick Lesters code A* path finding for beginners and see the lengths he goes to to ensure he gets fast performance.

 

I've used this technique to good effect but there is a trade off in performance with increasing grid size. I have found it's best not to go much over 100 X 100 (10,000 nodes) and have implemented a system of linking grids to extend the coverage to anything you want. My system also speads the work over multiple game loop iterations which also helps maintain good framerates whilst path finding for lots of NPCs.

 

As Niosop suggests, using nav mesh based systems like Recast is undoubtably better but a lot more involved. Thankfully Mikko Mononen has done virtually all of the really hard work for you but I know it still took Chris about 3 months work to get it integrated properly along with steering.

 

I looked at micro panther which is a more generic A* solver but decided in favour of Patrick's approach which really gave me the speed I was looking for.

 

You just need to look at techniques for keeping the memory usage down and the performance up, and then craft a system that works for you and meets your requirements.

 

Oh, and for anyone else who might be interested, don't ever use Lua for the low level stuff, it will simply kill the performance dead! It's an interpreted scripting language and was never designed for jobs like this!

 

Pic of my navArea Editor showing the grid system and auto calculated non walkable nodes (minimal interface I know ... but it works really well and is easy to use):

 

 

The system works with varying height terrain too, not just flat surfaces.

[Niosop]

Looks nice Pixel. The only reason I suggested MicroPather is because it has a nice setup that works fine w/ a grid, but doesn't require it as you can define your own connections between nodes. The approach I'm currently working on sets nodes just along the corners of obstacles which reduces the number of iterations by 100x or so for mid sized/moderately populated maps and uses raycasts every 10 frames or so to tell if you can get directly to the target in which case it won't use pathfinding. Going to make it run as a DLL and write a Lua wrapper so lua scripts can request a path from the solver. So pathfinding will work the same in the editor as it will in the game.

[Pixel Perfect]

Yes, micro pather is more flexible in that respect. I use a modified version of Patrick's code to do the same when finding a path through multiple navAreas as that no longer fits a uniform grid model.

 

Your approach sounds interesting too and yes I agree with the ray casting, pointless requesting a pathfind if you can ascertain a direct path is available anyway. Your goal of having it work in the editor and the game sounds great, good luck with that!

[Shard]

If you want fast A* you shouldn't be using oop at all, it will just slow it down to much and take much more memory. Confine your use of OOP to higher levels. No one uses it in anything that really requires high performance. No need to store x, y co-ordinates etc because they are easy to calculate on the fly by virtue of the grid poisition. A simple byte array is really all that's needed to either store a 1 or a 0. The memory foot print would then be about 250K.[/qoute]

 

Great idea. I had not thought of that one and it makes a lot of sense. I will defintiely fix it from ints to bools.

 

The system works with varying height terrain too, not just flat surfaces.

 

Does it work for multi level buildings? Like a three floor in door scene?

[Pixel Perfect]

[

Does it work for multi level buildings? Like a three floor in door scene?

No, it works for undulating ground like terrain (that is ... a single surface). In the example you give I would use three grids joined by linking waypoints on the stairways.

 

I have the concept of navAreas which are just square areas defined by placing two marker points in my editor representing the diagonal. These can be comprised of A* grids or 'navigation waypoints' (useful where you want to follow paths or roads in large outdoor situations) or a navArea can be comprised of both allowing you to switch from one to the other. The navAreas are linked via one or many 'linking waypoint' pairs. You can have as many navAreas as you want and mix and match the types. In addition to this 'info waypoints' can be placed anywhere in a navArea to store information for AI.

 

So requesting a path from a location in NavArea A to a location in navArea D would result in the AI Manager initially finding a path between the 'linking waypoints' (nodes) to determine the sequence of navAreas traversed and then a path is computed through each navArea in turn. In practice in a fairly dynamic world you will only compute part of the path as by the time you have got that far things may well have changed and a new path request issued