I have a fairly unusual use of A* in my game, and I’m trying to come up with a good heuristic for it but so far I’ve done decently at best. So, here’s the situation:
You control cars driving around in a 2D grid that can range from being completely open to being maze-like. The cars can do the following:
- Cars can turn up to 90º over one grid space (i.e. a car moving forward can turn right or left immediately, or a shade in between).
- Cars can drive diagonally into another grid space.
- A car can go in reverse or drive forward, but going from one to the other (i.e. going in reverse a couple spaces then suddenly going forward) requires the car to pause momentarily.
My pathfinder started out being pretty simple, basically it would just use the Manhattan distance to decide the heuristic. When I added diagonals, I modified it slightly so that it would only use the biggest change in direction for the heuristic (of X and Y). That works pretty well if the cars can go in any direction at any time, but because of their whole driving forward, stopping, then driving backwards thing, this really changes the game. Similarly, someone in a car would tend to go in a straight line, rather than hugging walls and taking a lot of diagonals. So, I tried to add the turning into the heuristic function, but that can randomly give some pretty insane results (in one case, the car backs up, stops, drives forward, stops, then drives backwards again and moves to its target from there).
So I’m wondering if anyone has any insight for me that might help me out. I’m just sort of messing around now to try to get something that really works, but it seems every approach has a major problem.
Two heuristics I tried:
public float heuristicOne (PathData data, Point start, Point goal)
{
//Find the adjusted Manhattan distance from the goal.
float value = Math.max(Math.abs(p.x - data.space.x), Math.abs(p.y - data.space.y));
//Use the facing difference from the data to its parent data.
if (data.parent != nil)
{
//Change the divisor on this if you want the car to prioritize turning over distance.
//i.e. if you make this a multiple (like *8 or something) the car will try to turn as little
//as possible, barely taking the distance into account. Similarly if you make it /8 then
//the car will not care how many crazy turns it's got to make as long as it's a shorter path.
value += ( Math.abs(data.space.x - data.parent.space.x) + Math.abs(data.space.y - data.parent.space.y) ) / 2.0f;
}
return value;
}
public float heuristicTwo (PathData data, Point start, Point goal)
{
float dx1 = goal.x - data.space.x;
float dy1 = goal.y - data.space.y;
float dx2 = start.x - data.space.x;
float dy2 = start.y - data.space.y;
float cross = dx1 * dy2 - dx2 * dy1;
cross = Math.abs(cross);
return (Math.max(Math.abs(dx1), Math.abs(dy1)) + cross*0.0002f);
}
The first one is pretty typical in using the adjusted Manhattan distance, aside from the extra weight it adds for turning. Note that the X and Ys of the PathData “space” are indices, so a change in a space will be either: (0,0) (0,1) (1,0), (1,1), (0,-1), (-1,0), or (-1,-1) and nothing else. This means that the bigger a turn, the more expensive the resulting cost for it. Because every LevelSpace can only be accessed by another LevelSpace, I can use its parent’s location and its location to determine in what direction a turn was made for this space. But… actually looking at this now and trying to explain what it does I realize it’s all wrong, haha. Getting my thoughts out there in detail usually makes me see the problem anyway. Looks like what I have now actually will just make diagonal movements more expensive than straight ones, which wasn’t my intention. So, ignore that for now, I’ll fix it soon and repost.
The second one uses a fudged algorithm in order to have unique “tie” values (and therefore limit searching redundancy), but otherwise just uses the adjusted Manhattan distance again. Also, the heuristic has to be fast and doesn’t need to be particularly accurate, it just needs to look accurate.
So, any ideas on good heuristics for this?
EXIT here’s a fixed version of heuristic one. Just uses the (already stored) facing instead. Doesn’t seem to solve the problem of the cars choose semi-insane paths.
public float heuristicOne (PathData data, Point start, Point goal)
{
//Find the adjusted Manhattan distance from the goal.
float value = Math.max(Math.abs(p.x - data.space.x), Math.abs(p.y - data.space.y));
//Use the facing difference from the data to its parent data.
if (data.parent != nil)
{
//Change the divisor on this if you want the car to prioritize turning over distance.
//i.e. if you make this a multiple (like *8 or something) the car will try to turn as little
//as possible, barely taking the distance into account. Similarly if you make it /8 then
//the car will not care how many crazy turns it's got to make as long as it's a shorter path.
value += ( Math.abs(data.facing.x - data.parent.facing.x) + Math.abs(data.facing.y - data.parent.facing.y) ) / 2.0f;
}
return value;
}