Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (475)
Games in Android Showcase (106)
games submitted by our members
Games in WIP (530)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Interesting A* Pathfinding Heuristic  (Read 2824 times)
0 Members and 1 Guest are viewing this topic.
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11


Game Engineer


« Posted 2009-07-01 20:01:35 »

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:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
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;
}


1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
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.
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
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;
}

See my work:
OTC Software
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11


Game Engineer


« Reply #1 - Posted 2009-07-01 20:45:08 »

So actually what appears to work fairly well is the same algorithm above just with a lot more weight given to the turning costs.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
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) ) * 4.0f;
   }
   
   return value;
}


The only issue now is that the car will sometimes make a turn in a clockwise direction then suddenly make a counter-clockwise turn the next step. It looks pretty unnatural, of course, but I'm ignoring that for now because it rarely happens and when I added another level of complexity (to check for turns of conflicting direction) it screwed everything up again.

EDIT - I'm lying, this very often does not work at all (the car will completely refuse to go a certain way that it is allowed to go, I guess because the heuristic for the path exceeds its current space so it doesn't even view it as an option). Similarly, it will take some pretty dumb routes every once in a while.

EDIT2 - It occurs to me that how I'm computing cost may also be a problem - looks like I'm using the heuristic in some comparisons but not in others. Let me fix up my monkey code and maybe it'll work better.

See my work:
OTC Software
Offline Jono
« Reply #2 - Posted 2009-07-12 00:45:04 »

The problem with insane paths in heuristicOne is probably caused by that multiplier. For A* to guarantee the shortest path, the heuristic has to be admissible - it always has to return a value lower or equal to the actual distance to the goal. So the *4 or *8 might pop it over that threshold.

Is your g(x) function (the cost so far) a measure of the distance travelled so far or the time taken so far? If it's currently just the distance then switching it over to be the time cost, including pauses for reversing etc., then that could make a big difference.

The cross*0.0002 idea in heuristicTwo is a way I've used before to get preference for not taking too many turns. However, I'd put the penalty into the cost function rather than the heuristic, because the heuristic just guides the search while the cost function changes the preference for a final path. And just make sure that the penalties for turning over the whole path never add up to more than one move forward (to keep the heuristic admissible).
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

ctomni231 (33 views)
2014-07-18 06:55:21

Zero Volt (29 views)
2014-07-17 23:47:54

danieldean (24 views)
2014-07-17 23:41:23

MustardPeter (26 views)
2014-07-16 23:30:00

Cero (41 views)
2014-07-16 00:42:17

Riven (43 views)
2014-07-14 18:02:53

OpenGLShaders (31 views)
2014-07-14 16:23:47

Riven (30 views)
2014-07-14 11:51:35

quew8 (29 views)
2014-07-13 13:57:52

SHC (65 views)
2014-07-12 17:50:04
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!