Multiple pathfinders and memory usage

Game Mechanics Artificial Intelligence
#1

Hey

I’m planning on using A* for pathfinding in my (next) game. I’ve already implemented it before (so I have full understanding of it), but there is one thing that I don’t know how to solve and it’s not really related to A* directly.

Since my game is going to be a RTS-kind, there may be multiple units trying to find a path, so I’m going to have a pool of let’s say 3-5 pathfinder threads ready to find a path for any of those units in the game (async.)

Now, the way I implemented A* before was in a tile based grid;

  • Each tile was represented by a node, and each node had a list of it’s neighbors.
  • So once I knew the start and goal nodes I could easily expand the search area by retrieving the neighboring nodes. (straight-forward!)
  • However, it is only possible to execute one pathfinding operation at a time on the same set of nodes. This is because I use the nodes, define values in them, like if the node is “visited”, the “parent” node, and the costs (estimated and totalfromstart).

How can I have more than 1 pathfinding thread searching in the same set of data (nodes) at the same time without duplicating all the nodes for each pathfinder?

Hopefully my question is making sense.

Also, tips on how to best implement a PathfindingResourcePoolManger are welcome :slight_smile:

#2

Simple answer; Don’t have one node per tile. Keep a stack of nodes. The thing following the path only needs to know the actual path, so your pathfinding routine can discard useless nodes after the path is found. In other words; separate the pathfinding from the map. Depending on the complexity of the map this method should use less memory too…

#3

Hey

Yes, I do seperate the pathfinding grid nodes from the map tiles. That is, I might have a int[ ][ ] array for the map and a Node[ ][ ] array for pathfinding.

However, would I need to duplicate the Node[ ][ ] array for each pathfinder? I don’t like it, but hm… what do you mean by a “Stack of nodes”?

#4

The way I’ve done it (a year ago) was to have Node and PathElement. Each PathElement contains the reference to a Node and the data specific to calculating the given path. After the Path was not needed any more, the PathElement objects were put back into and array, and reused when constructing another path.

#5

But in worst cases you’ll need the same same number of PathElements for a Pathfinder as there are Nodes in the map, so it really defeats the purpose, might as well just use and duplicate the Nodes for each Pathfinder.

Example; if you try to find a path that does not exist, e.g. the goal node is trapped, then you might need to explore ALL nodes that are accessible from the start node.
Imagine a tilemap grid where all tiles are passable, except the goal tile is located in one corner and is enclosed by 3 blocking tiles. You would need to explore all the tiles except those 4.

#6

You can create a copy of the nodes if the size is manageable, but there are some other strategies:

Maintain sets of interconnected nodes, so with one single check you can make sure that a path exists. If all the nodes are interconnected, there will be only one set.
Limit the depth of the search. I had about 20K nodes, and the search was limited to 10K nodes. The reasoning was: if it takes a so complicated route to get there, the game situation will change so much, that the AI will need to do something else anyway.
The good thing in A* is that it can provide the closest node to target, no matter if the target is unreachable.
I allowed paths which didn’t get to the target, but were close enough to “see” the target.

#7

[quote=“appel,post:3,topic:31102”]
I mean don’t use arrays but Lists. Take a look here

#8

Hey SimonH

I’ve been doing very similar as in that tutorial, however that tutorial only allows for one pathfinder at a time working on the set of nodes.

The way I’ve created the nodes for the pathfinding is:

  1. Create the two-dimensional tilemap, e.g. Tiles[128][128] - this is not used in the pathfinding
  2. Now I create a two-dimensional array of Node[128][128], e.g. Node [10][20] represents Tile[10][20]. - these nodes I’m going to use in the pathfinding.
  3. Once the Node array has been created I loop through it, and for every node in the array I create a List of all it’s neighbours (adjacent and diagonal to that node). I simply do something like: neighbour.add(nodes[x-1][y-1]) etc.
  4. Now all nodes have their neighbours defined.

The above has several cons I’ve discovered:

  1. Memory consuming, although it’s ok for 1 pathfinder, it’s probably not so good if I have multiple pathfinders. There must be a better way than to have 5 x Node[128][128] for 5 x pathfinders.
  2. My game allows for diagonal movement, and I want the cost of diagonal movement to be larger than adjacent movement. This complicates things, now I need to know the physical location of the nodes, or at least how that node it attached, either adjacentally or diagonally, in order to calculate the correct cost.

I’d like to keep my pathfinder very general, so I can feed into it whatever start and goal nodes without it worrying about their physical locations (e.g. x and y). Not sure how calculating diagonal/adjacent cost fits into this idea.

Anyway, hopefully this explains my problem a bit better.

#9

My point is that you don’t need the Node[][] array - the map tells you where you can and can’t go

Here’s my (fairly generic) a* code;

NB for diagonal moves modify the ‘+1’ in getNeighbours() to ‘+sqrt(2)’ to add to the cost


public class PathNode
{
	int x;
	int y;
	double cost;
	double dist;
	PathNode parent = null;

	public PathNode(int xIn, int yIn, double costIn, double distIn) {
		x = xIn;
		y = yIn;
		cost = costIn;
		dist = distIn;
	}
}

/******************************************************************
 * getNeighbours
 * function used in pathfinding
 ******************************************************************/
	private Vector getNeighbours(int x, int y, double cost, int tx, int ty) {
		Vector list = new Vector();
		for (int dx=-1; dx<2; dx++)
		{
			for (int dy=-1; dy<2; dy++)
			{
				if ((dx != 0) || (dy != 0))
				{
					if ((x+dx>-1) && (x+dx<gridWidth) && (y+dy>-1) && (y+dy<gridHeight))
					{
						int content=readMap(x+dx,y+dy);
						if (content==EMPTY) // if empty
						{
							double dist = range(x, y, tx, ty);
							list.addElement(new PathNode(x + dx, y + dy, cost + 1, dist));
						}
					}
				}
			}
		}
		return list;
	}
/******************************************************************
 * removeFromList
 * function used in pathfinding
 ******************************************************************/
	private void removeFromList(Vector v, PathNode p) {
		Enumeration e = v.elements();
		while (e.hasMoreElements()) {
			PathNode nn = (PathNode) e.nextElement();
			if ((nn.x == p.x) && (nn.y == p.y)) {
				v.removeElement(nn);
				return;
			}
		}
	}
/******************************************************************
 * addToOpen
 * function used in pathfinding
 ******************************************************************/
	private void addToOpen(Vector open, int x, int y, double cost, double dist, PathNode parent) {
		PathNode node = new PathNode(x, y, cost, dist);
		node.parent = parent;
		if (open.size() > 0) {
			for (int i=0; i<open.size(); i++) {
				PathNode p = (PathNode) open.elementAt(i);
				if (p.cost > cost) {
					open.insertElementAt(node, i);
					return;
				}
			}
		}
		open.addElement(node);
	}
/******************************************************************
 * checkIfGot
 * function used in pathfinding to avoid duplication of squares
 ******************************************************************/
	private boolean checkIfGot(Vector v, PathNode p) {
		Enumeration e = v.elements();
		while (e.hasMoreElements()) {
			PathNode nn = (PathNode) e.nextElement();
			if ((nn.x == p.x) && (nn.y == p.y)) return true;
		}
		return false;
	}
/******************************************************************
 * findPath
 * entry function used in pathfinding
 ******************************************************************/
	public Vector findPath(int sx, int sy, int tx, int ty) {

		Vector path = new Vector();
		Vector open = new Vector();
		Vector closed = new Vector();

		int count = 0;

		if ((sx == tx) && (sy == ty)) {
			path.insertElementAt(new PathNode(tx, ty, 0, 0), 0);
			return path;
		}

		double dist = range(sx, sy, tx, ty);
		addToOpen(open, sx, sy, 0, dist, null);

		while (!open.isEmpty())
		{
			PathNode pn = (PathNode) open.elementAt(0);
			open.removeElementAt(0);
			if ((pn.x == tx) && (pn.y == ty)) {
				// path found
				while (pn.parent != null)
				{
					path.insertElementAt(pn, 0);
					pn = pn.parent;
				}
				return path;
			}
			// get neighbours
			Vector neighbours = getNeighbours(pn.x, pn.y, pn.cost, tx, ty);
			count++;
			// check each neighbour
			Enumeration e = neighbours.elements();
			while (e.hasMoreElements())
			{
				PathNode nn = (PathNode) e.nextElement();
				// check if in open & closed
				boolean isInOpen = checkIfGot(open, nn);
				boolean isInClosed = checkIfGot(closed, nn);

				double cost = pn.cost + range(pn.x, pn.y, nn.x, nn.y);

				if ((!isInOpen) && (!isInClosed) || (cost < nn.cost)) {
					nn.parent = pn;
					nn.cost = cost;
					if (isInClosed) removeFromList(closed, nn);
					addToOpen(open, nn.x, nn.y, nn.cost, nn.dist, nn.parent);
				}
			}
			closed.addElement(pn);
		}
		return null;
	}
#10

Thanks for your code.

But I raise both of my eyebrows when I read it.

First, your A* is very dependant upon knowing it’s surroundings. I feel this is not what A* is supposed to know, sort of like cheating :). What if you had a regular graph of nodes, e.g. where nodes can have anywhere from 1 to 10 neighbours (or more!). I’m not saying your method is wrong, but I’m creating a pathfinding package that is supposed to be abstract enough for both uses.
E.g., your A* wouldn’t work on hexagonal grid where each tile has 6 neighbours instead of 8.

Second, holy holy!! Your getNeighbours(…) method is a HUGE performance bottleneck. I’ve implemented A* that way before, and it’s anywhere from 10-20 times slower than using a pre-existing nodes. Not to mention GC overhead because of all those “new’s”. Also, in those worst-case scenarios I talked about you might need to create just as many PathNode’s as there are tiles on the map (subtracting 3). You could never use this in a proper computer game where you might have hundreds, or even dozens, of entities requesting path every minute or so.

Third, your methods “checkIfGot()” and “removeFromList()” are both O(n), which is not optimal. These should be O(1) IMO, if you want your A* to be quick.

Fourth, I’m not sure, but I’m not confident in your cost calculations.
You seem to do “double cost = pn.cost + range(pn.x, pn.y, nn.x, nn.y);” for calculating the cost from the start. This doesn’t consider that tiles can have different cost, e.g. hill tile vs. road tile where the tank should avoid the hill tile. Also, I find it strange that you need to do euclidean distance calculation between two adjacent tiles! This can be easily fixed though, and I’m sure your A* implementation works fine without this.

In a way your A* implementation does solve my multithreading problem, but it however introduces many bad things.

Hopefully my comments are well taken :slight_smile:

#11

[quote=“appel,post:10,topic:31102”]
Sorry, Sir! I’ll do it again only better! :wink:

This was written ages ago for an app where code legibility was more important than speed (that’s why I posted it!).
It’s not that dependent on surroundings though - the getNeighbours() function is all that needs changing…
I agree that it can be vastly imporved, but the important thing is the separation between the map and the pathfinding code.

#12

nm, I’ve decided this is more trouble than it’s worth. I’ll just make my pathfinder and make if a 2D grid specific.

#13

it has been months since you posted this, but here is my 2 cents…

i do the same in my A* implementation too. that’s a good thing for performance IMHO.

my short answer is dont :wink: why do you need spreading pathfinding amoung multiple threads ? more threads wont give you any more cpu time. they’re mostly useful to parallelize blocking operations like i/o. it’s true you can benefit from dual-core cpu’s by spawning a thread for pathfinding but even in that case one pathfinding thread will be enough. just queue the pathfind requests in that thread

but, if you really really want to spawn a thread for each pathfind request, you need to decouple A* information from your nodes: that is, move f, g, h and parent fields from node to another class (say NodeAData) and some how lookup for them. if each of your nodes has a unique id, you may put them into a HashMap or so (and face the lookup performance issues ;)). or assigning an id to each pathfind request, and allow your nodes to hold more than one NodeAData maybe another option. this will reduce the lookup time, but you will need to clean them later

hope this helps,
r a f t

#14

cant you try the solution I told about there ?

http://www.java-gaming.org/forums/index.php?topic=17924.0

I mean using a temporal dimension ? as if you were using a 3D array rather than a 2d Array with third dimendion representing turn/time, one unit can only be in one 2d pos for a given 3d/temporal index this way you do not have to make parrallel path search. but just a 3 dimension path finder once an unit find a path, this path is stamped as occupied than you find for unit two, than unit three, etc…

#15

you are talking about cooperative pathfinding. but as described in that paper, if you only add a 3rd dimension as time to your search space and use same heuristic as before, you will run into performance issues (possibly not noticable for small maps) you need some other heuristic like that true distance heuristic feeded by reverse A* search. in that case I argue that it’s simple to implement

#16

I’ve discovered that it is sufficient to run one pathfinder in a thread, on recent computers there is no fps drop.

#17

There has been said a lot already, I might repeat some but I must admit I didnt read everything:

  1. Finding 5 paths the same time would actually not be faster than finding 5 paths sequentially. The CPU has the same amount of work to do, plus thread scheduling. Concurrent threads would give you an advance, when you have one big and one small search, the small one would be done soon and does not have to wait for the big one.

  2. Pathfinding information does NOT belong to the node. Either you keep a visited list with nodes, or you use a PathFindingNode object which keeps reference to a node. Both ways, you can use map nodes concurrently.

  3. Groups of units can share a pathfinding. Either all use the same path or you move the path of each one by its distance to the starting cell of o the search. But it can happen that a moved path runs into an obstacle, so you must check and correct such paths, but its still cheaper than searching again.

-JAW

#18

Hi, I like to know how to create logic for a weapon in the game which should not make a close circuit while place it on the game screen.
Its like there are (x,y) number of rows and columns. The user is allowed to place the weapon on the screen. The screen looks like a chess board. Full of odd number of rows and columns in the shape of squares.
Now the user can place the weapon on these squares so that as and when the enemies come they detect using collusion and the if its on firing range they fire to the enemy.
So now the weapon can be placed such that it should not form a closed circuit, that is it should leave one square empty so that the enemy moves out.
The enemy has a start state and a goal state. And it moves in the form of elephant of a chess game.
The enemy starts from say suppose top of a screen and moves one one square and doj’s the weapon and reaches other end of the screen.
SO i like to know how to stop the weapon from making a closed circuit?

In all total there are 9 columns and 11 rows, in all total 99 squares of 24 x 24 ok.
Weapons are places inside the squares. But it should not make a close circuit. Means I cannot block the whole row full of weapons. Say there should be a 24 x 24 cell left for the enemy to move around.

If i create a square or rectangle ,I should leave a 24 x 24 cell left so that the enemy passes through, from start state to the goal state.

For enemies I use A* algo. but for placing the weapons…dont know how.

The game is like iphone field runner. Kindly see the video in youtube and see how the weapons are placed and help me.

#19

Please stop spamming the forum with the same question. Nate has already given you the answer.