Bugger, now my naive A* implementation isn’t fast enough 
Who can make me a fast one with the appropriately quick datastructures backing it? I’ve got upwards of 300 entities wandering around a fairly simple grid topology of around 256x256 in size. It’s got to be very fast indeed.
Cas 
how is your A* working atm, do you calculate an A* path for every entity movement?
is it grid based pathfinding or mesh nodes?
you could do something like have a simple line check, straight to an entities destination, if nothings is in the way then you can skip the A* altogether and just move the entity there directly.
Another option, which would be much lighter on cpu would be to not use A* at all and go for something like steering behavior, this is very light on cpu and good for avoiding simple obstacles.
Flow Fields could also work pretty well for a tower defence game, again faster and cheaper then A*.
Grid based is gonna be really expensive for that many units anyway, you really need to use some sort of nav mesh instead, this will be massively faster.
if you must use grid based, you should looking into implementing something like HPA* (or MM Abstraction) instead of pure A*, it’ll be much quicker then A* especially for long paths.
Basically its tiered path finding where you have a high level grid (large squares) then a low level grid (smaller and finer detail), paths are calculated using the high level grid and then units move along it using the low level grid. Much faster then A* but uses slightly more memory.
If you’re still using the same AStar class from ages back, I got a decent speed up by switching the closed list to a HashMap mapping nodes of the same location onto themselves. You should be able to replace the open list with a TreeMap as well to remove even more linear list scans.
If that’s not enough I’d be tempted to go with flow fields + steering behaviours for the smaller droids, and only use A* for the bigger enemies. Or since your map is quite small you could go with ‘smell’ based pathfinding like some roguelikes use.
In addition to the previous question about your graph, what heap are you currently using, and what heuristic? Also, are the costs special-cased in any way (e.g. boolean)?
Probably teaching my grandmother to suck eggs here, but …
I had similar issues with this years Assassins4k entry and solved it by:
i) When the player leaves a room (in this case grid square) I calculate A* from the player to every location in the map, storing a ‘NSEW’ direction ‘to the player’ on each room in the first location in an array of direction indicators.
ii) The rest of the array of direction indicators is filled with precalculated A* searches for random locations.
Each entity follows one of the A* paths and when it reaches the end selects another path. Entities in attack mode alternate between following path 0 (which always leads to the player) and a random pre-calculated path.
This does mean that enemies attacking the player dynamically change direction as the player moves, and take no account of line-of sight visibility - the player cannot run round the corner and hide. On Assassins4k I ignored this.
On my StormTheCastle engine, I solved this by copying the current best route to the player onto the entity as a list, whenever the current A* ran out (provided the player was line-of-sight visible). If the player isn’t visible, the entity drops out of attack mode. Really one should do the copy whenever the player is visible, but this costs more and in practice the difference isn’t noticeable. The copy operation is cheaper than the full A* search.
The precalculated routes do make the entities go anywhere. If they have to stay local to a particular location, then they need to be grouped into areas, or you need to calculate a set per entity on the fly, whenever the entity goes into patrol mode. Two routes might be sufficient. On my StormTheCastle engine, all routes are converted to a set of velocity/time pairs, so patrol routes are independent of location and can be precalculated. If the entity hits something, it marches in place, until the next velocity/time pair is scheduled. Not perfect, but saves on A* searches.
Conclusion
If you have a lot of entities attacking the player, then this comes out cheaper than recalculating A* every time an entity finishes their current path. If the entities are attacking other entities, then this doesn’t provide much of a saving.
Edit: You can see the StormTheCastle A* implementation in action. This is a really old version and doesn’t work well on the Mac (low frame rate due to poor choice of image format causing endless conversions). The enemies are a bit too persistent too. Fixed on later unpublished version.
http://homepage.ntlworld.com/alan.d.waddington/demo/GameEngineDemo.html
Edit2: Just realised that I don’t limit max depth on my A* search, which I should for large maps. Added to my to-do list
Edit3: Found that I do limit on the cost function, which is distance: Deleted from to-do list.
Sorry for tardy reply - busy etc.
So: here’s where I’m at.
The grid size is at most 256x256, which covers a map more than 10 screens wide. This isn’t an entirely unreasonable grid size I think. I’d like to have been able to use hierarchical grids but due to the nature of the grid’s contents and the way the game plays, proper A* is really the only way to go here. The turrets, when placed down, subtly alter the cost of traversing nearby squares, and these subtle costs overlap, etc, meaning we get a quite complicated difficulty map. The way the player places turrets is significant as it essentially corrals the gidrahs into certain pathways, and it’s essential for strategy. I don’t think it’d work very well if I tried the low-res grid on top approach.
There’s no player as such; each gidrah can have one of many, many possible destinations, depending on its own personal strategy. The destinations are chosen very simply, and then A* finds out how to get there. The gidrah will simply ignore any buildings en route with the exception that certain buildings influence the difficulty of grid squares nearby as outlined above. Anything they collide with, they attack. At any rate, this means I can’t do a nice simple pre-calc of all possible paths on the map from every location because the destinations are dynamic and change over time, and additonally the map topology changes over time too, and different gidrahs have different ideas about what sort of difficulties they can cross (basically: stupid gidrahs will try to run past turrets and get killed unless there are a lot of turrets there; clever gidrahs will skirt around them).
Now, every gidrah has its own A* pathfinder; however, they all spawn from the same points, and there is a route cache which I store (and age over time and discard after a while). The route cache stores the path between any start point and any end point on the grid (it would be nice to have a data structure which somehow indexed all the points on the path in between too, which would make things even more efficient). If the route is determined to be clear of total obstacles when a gidrah’s on the start point, it bypasses A* completely. About 75% of the path finding at the start of a level follows this path as the gidrahs all spawn in the same locations - the first gidrah finds the initial route, and then the next gidrah just picks it up from the cache. It’s when they get close to their destination that things start to slow down as they aren’t allowed to directly walk through each other, so they start doing lots of frantic pathfinding - fortunately quite close to the target.
The heuristic (from memory, I’m @ work) is a very simple h = distance, which as the gidrahs are allowed to walk in diagonal lines for approx 1.42x the normal cost of a move, gives nice natural direct looking paths over the grid to targets. It’s just wibbly enough through chance that it looks more natural.
Now, with 500 gidrahs all attempting to find a path every frame you wouldn’t be entirely suprised if the framerate was rather bad, so they’re limited to a maximum of just a few steps each frame; so I was looking at maybe 1000 A* steps per frame, which I hadn’t thought would be that expensive. I thought wrong
Orangy - yes, I was using that simple A* class in SPGL. I’m halfway through converting it to use TreeMap for the open list and HashMap for the closed list; last night I got it all to compile but it’s just hanging during a search now. My fear was that I was abusing the use of TreeMap: the comparator uses the f value of a node, and therefore node.compareTo(otherNode) == 0 when their f values are the same. However, the node.equals() method compares userState, not f; I wonder if this is causing me problems. It’s supposed to work, I think, according to the TreeMap docs.
I expect TreeMap and HashMap are going to massively speed up the A* implementation so I will let you know if it solves my problem. If I can reliably get 500 gidrahs swarming towards the player’s buildings at 60fps on my rubbishy laptop I will consider that a success (and ooh you are really going to enjoy setting up a massive array of defences to mow them down!!)
Cas
Costs are either -1 for impassable, or a float value describing the difficulty of the move, based on 1.0 for NSEW movement, and adding certain amounts based on nearby danger. I think by heap you mean the TreeMap I’ve just put in last night…?
Cas
I find TreeMap a tricky beast, which is a shame because it’s damn powerful. IIRC TreeMap expects two nodes that are equal() to also have compareTo()==0, so your compareTo() should check userData first and return 0 if they’re identical. At least something very similar to that was tripping me up.
How’s about: a route is planned at spawn, and perhaps whenever the routing conditions substantially change (player deploys a turret on the planned path, etc), and then use steering behaviours to follow the path and take care of the overcrowding drama, like this. Once the gidrah is close enough to the target, I’d imagine that purely using steering behaviours would be sufficient to find a space at the target building.
It’ll give you loads of parameters to tweak for different unit types:
So: A* for the global strategic planning, steering behaviours for the local interactions.
I don’t know that steering will really solve any problems here - the interactions only really come into play when they’re very close to their target usually, so the actual length of time spent searching for a path is much smaller than it might otherwise be anyway.
Besides I have no idea how to implement steering behaviour 
Cas
Ok, so probably no cunning tricks to be played there.
[quote]I think by heap you mean the TreeMap I’ve just put in last night…?
[/quote]
“Priority queue” is another name for it. I can’t work out where in SPGL (assuming the SourceForge CVS at http://spgl.cvs.sourceforge.net/viewvc/spgl/ to be up-to-date) the A* implementation is hiding, so I can’t see what the map is from and to, but TreeMap doesn’t sound like a great solution to me. IIRC it’s a self-balancing tree. A simple binary heap should be more efficient.
I’d love a simple binary heap class, but there isn’t one in the JDK is there?
Can anyone provide one that just uses ints?
And not forgetting that it needs to sort on f but be able to add and remove based on userState (both f and userstate are ints though so no nasty objects or casting needed).
The SPGL A* is possibly in spgl-extra in the algorithms package. I’ve already altered it a bit for this game so it has pluggable topology.
Cas
PriorityQueue. It’s not great at arbitrary removal, though.
[quote]Can anyone provide one that just uses ints?
[/quote]
I thought you just said your costs were floats? Or are you looking for a queue whose elements are ints with priorities which are floats?
[quote]And not forgetting that it needs to sort on f but be able to add and remove based on userState (both f and userstate are ints though so no nasty objects or casting needed).
[/quote]
It seems to me that the easy approach here is to make the heap just handle Nodes and make the Map handle the mapping between userState and nodes. The Map can do this with a simple array lookup.
PriorityQueue - bugger.
I can make my costs into ints pretty easily if it makes my life easier
I’m a bit confused as to how I’d do your last suggestion - the heap is what, again? And how do I synchronize the heap with a map?
Cas
It should handle your crowding problem. I imagine a gidrah’s thought process currently goes something like
So you’re spending time planning routes that are invalidated pretty quickly by the movement of other gidrahs. I imagine you also see gidrahs dithering back and forth as they follow these abortive routes.
Implementation is pretty easy, especially as gidrahs don’t have momentum - the overall motion arises from the combination of trivially simple behaviours:
Each behaviour results in a desired movement vector: just add them up (weighted appropriately), normalise to the gidrah’s movement speed, and add to the position.
I’ve had a quick go at implementing a simple target-seeking, collision-avoiding behaviour. Results here, code here. Some interesting behaviour (fast gidrahs barging through crowds of their slower peers, making room for late arrivals at the target point, etc) from simple rules of motion.
I’ll give you the public signatures before the full code:
public class BinaryHeap<E>
{
public Node<E> insert(E userData, float cost);
public Node<E> peek();
public Node<E> pop();
public void remove(Node<E> node);
public void changeCost(Node<E> node, float newCost);
public int size();
public static class Node<E>
{
public E userData;
}
}
This is a data structure for the open list. You’ll probably want to adapt it to replace with the primitive int, but that’s a minor detail. The point is that the mapping from user data to the Node is done externally: if you don’t want to support removal then you can ignore it, but if you do then it’s up to the caller (in this case the A* implementation) to maintain the mapping from user data to Node. I’ve done it this way specifically to support your use case, because you can use a linearised array to do the mapping.
The code, plus a few unit tests to check that I haven’t bodged my parent/child index calculations. The changeCost method isn’t currently tested.
package com.akshor.pjt33.util;
import static org.junit.Assert.assertEquals;
import org.junit.Test;
public class BinaryHeap<E>
{
@SuppressWarnings("unchecked")
private Node<E>[] heap = new Node[128];
private int size = 0;
public Node<E> insert(E userData, float cost)
{
Node<E> node = new Node<E>();
node.userData = userData;
node.cost = cost;
// Expand if necessary.
if (size == heap.length)
{
@SuppressWarnings("unchecked")
Node<E>[] newHeap = new Node[size << 1];
System.arraycopy(heap, 0, newHeap, 0, size);
heap = newHeap;
}
// Insert at end and bubble up.
heap[size] = node;
node.heapIdx = size;
upHeap(size++);
return node;
}
public Node<E> peek()
{
return heap[0];
}
public Node<E> pop()
{
Node<E> popped = heap[0];
heap[0] = heap[--size];
heap[size] = null;
if (size > 0) downHeap(0);
return popped;
}
public void remove(Node<E> node)
{
// This is what node.heapIdx is for.
heap[node.heapIdx] = heap[--size];
heap[size] = null;
if (size > node.heapIdx)
{
if (heap[node.heapIdx].cost < node.cost)
{
upHeap(node.heapIdx);
}
else
{
downHeap(node.heapIdx);
}
}
// Just as a precaution: should make stuff blow up if the node is abused.
node.heapIdx = -1;
}
public void changeCost(Node<E> node, float newCost)
{
float oldCost = node.cost;
node.cost = newCost;
if (newCost < oldCost)
{
upHeap(node.heapIdx);
}
else
{
downHeap(node.heapIdx);
}
}
public int size()
{
return size;
}
private void upHeap(int idx)
{
Node<E> node = heap[idx];
float cost = node.cost;
while (idx > 0)
{
int parentIdx = (idx - 1) >> 1;
Node<E> parent = heap[parentIdx];
if (cost < parent.cost)
{
heap[idx] = parent;
parent.heapIdx = idx;
idx = parentIdx;
}
else break;
}
heap[idx] = node;
node.heapIdx = idx;
}
private void downHeap(int idx)
{
Node<E> node = heap[idx];
float cost = node.cost;
while (true)
{
int leftIdx = 1 + (idx << 1);
int rightIdx = leftIdx + 1;
if (leftIdx >= size) break;
// We definitely have a left child.
Node<E> leftNode = heap[leftIdx];
float leftCost = leftNode.cost;
// We may have a right child.
Node<E> rightNode;
float rightCost;
if (rightIdx >= size)
{
// Only need to compare with left.
rightNode = null;
rightCost = Float.POSITIVE_INFINITY;
}
else
{
rightNode = heap[rightIdx];
rightCost = rightNode.cost;
}
// Find the smallest of the three costs: the corresponding node
// should be the parent.
if (leftCost < rightCost)
{
if (leftCost < cost)
{
heap[idx] = leftNode;
leftNode.heapIdx = idx;
idx = leftIdx;
}
else break;
}
else
{
if (rightCost < cost)
{
heap[idx] = rightNode;
rightNode.heapIdx = idx;
idx = rightIdx;
}
else break;
}
}
heap[idx] = node;
node.heapIdx = idx;
}
/**
* We assume that the user will be sensible with this! The design is aimed
* at people who have common sense and want efficiency.
*/
public static class Node<E>
{
/*package*/ float cost;
/*package*/ int heapIdx;
public E userData;
}
@Test
public void regressionTestOne()
{
BinaryHeap<String> heap = new BinaryHeap<String>();
heap.insert("A", 0);
heap.insert("B", 1);
assertEquals("A", heap.pop().userData);
heap.insert("D", 3);
heap.insert("L", 11);
assertEquals("B", heap.pop().userData);
heap.insert("K", 10);
heap.insert("C", 2);
assertEquals("C", heap.pop().userData);
heap.insert("E", 4);
assertEquals("D", heap.pop().userData);
heap.insert("I", 8);
heap.insert("H", 7);
assertEquals("E", heap.pop().userData);
heap.insert("F", 5);
assertEquals("F", heap.pop().userData);
heap.insert("G", 6);
heap.insert("J", 9);
assertEquals("G", heap.pop().userData);
assertEquals("H", heap.pop().userData);
assertEquals("I", heap.pop().userData);
assertEquals("J", heap.pop().userData);
assertEquals("K", heap.pop().userData);
assertEquals("L", heap.pop().userData);
assertEquals(0, heap.size());
}
@Test
public void downHeapLeft()
{
BinaryHeap<String> heap = new BinaryHeap<String>();
heap.insert("A", 0);
heap.insert("B", 1);
heap.insert("C", 2);
heap.insert("D", 3);
assertEquals("A", heap.pop().userData);
assertEquals("B", heap.pop().userData);
assertEquals("C", heap.pop().userData);
assertEquals("D", heap.pop().userData);
assertEquals(0, heap.size());
}
@Test
public void downHeapRight()
{
BinaryHeap<String> heap = new BinaryHeap<String>();
heap.insert("A", 0);
heap.insert("C", 2);
heap.insert("B", 1);
heap.insert("D", 3);
assertEquals("A", heap.pop().userData);
assertEquals("B", heap.pop().userData);
assertEquals("C", heap.pop().userData);
assertEquals("D", heap.pop().userData);
assertEquals(0, heap.size());
}
@Test
public void testRemovalDownheap()
{
BinaryHeap<String> heap = new BinaryHeap<String>();
heap.insert("A", 0);
Node<String> nodeB = heap.insert("B", 1);
heap.insert("C", 2);
heap.insert("D", 3);
heap.insert("E", 4);
heap.insert("F", 5);
heap.remove(nodeB);
assertEquals("A", heap.pop().userData);
assertEquals("C", heap.pop().userData);
assertEquals("D", heap.pop().userData);
assertEquals("E", heap.pop().userData);
assertEquals("F", heap.pop().userData);
assertEquals(0, heap.size());
}
@Test
public void testRemovalUpheap()
{
BinaryHeap<String> heap = new BinaryHeap<String>();
heap.insert("A", 0);
heap.insert("B", 3);
heap.insert("C", 1);
Node<String> nodeD = heap.insert("D", 4);
heap.insert("E", 5);
heap.insert("F", 6);
heap.insert("G", 2);
// Heap currently looks like
// A:0
// / \
// B:3 C:1
// / \ / \
// D:4 E:5 F:6 G:2
//
// If we delete D, swapping G up, then we get:
// A:0
// / \
// B:3 C:1
// / \ /
// G:2 E:5 F:6
// Assuming we don't upheap, two pops will remove A and C (swapping and
// down-heaping F and E) and the third will remove B. If we tried to use
// the minimum test case (F:2, no G) then although we would have an
// inconsistent intermediate state we would pop out in the correct
// order, because popping() C would put F to root and downheap it.
heap.remove(nodeD);
assertEquals("A", heap.pop().userData);
assertEquals("C", heap.pop().userData);
assertEquals("G", heap.pop().userData);
assertEquals("B", heap.pop().userData);
assertEquals("E", heap.pop().userData);
assertEquals("F", heap.pop().userData);
assertEquals(0, heap.size());
}
}
Oooh, that’s brilliant, I’ll try that at home tonight when I get back from work.
I got the algorithm working with TreeMap in the end but it had issues. Finding the head to pop was easy enough; however, actually removing the head (or doing a contains(), or get(), based on userstate) was very slow, as it required a treeMap.values().contains()… and that seemed to do a copy of the whole TreeMap into another Collection of some sort. So it was generating a meg of garbage every second, and the Comparator used by the TreeMap was costing over 10% of the compiled code time - arrgh. All in all when I got to about 100 gidrahs it was costing 15ms / frame just to do 500 A* iterations!
So I can’t wait to try out this extremely lean-looking binary heap class. I’m quite surprised this structure doesn’t already exist in the JDK, as it’s very well documented all over the internet.
Cas
I think the off-the-shelf java.util.PriorityQueue is implemented as a binary heap.
It is, but it has O(n) operations to remove an element or reduce its key, which makes it pretty pointless for Dijkstra/A*/C.