AI Pathfinding for Maze Puzzle

[KodiakBehr]

My apologies in advance, this is going to feature some really, really bad code as I'm making up the logic as I go with no direction or experience.  I may have bitten off more than I can chew, but I'd like to hear an expert opinion before I give up.

One particularly unique puzzle in a game that I am working on is to be based upon the "Theseus and the Minotaur" maze puzzle made in the early 90's.

The premise is simple.  You've got a grid-maze with two characters inside it, Theseus (the player) and the Minotaur.  If the Minotaur touches Theseus, it's game over for that latter.  For every one step made my the player, the Minotaur takes up to two.  The Minotaur's pathfinding logic is straightforward:

1  Can the Minotaur move horizontally and get closer to Theseus? If Yes, go to 2. If No, go to 3.
2.  Move Horizontally one grid-square towards Theseus. Then go to 5.
3.  Can the Minotaur move vertically and get closer to Theseus? If Yes, go to 4. If No, go to 5.
4.  Move vertically one grid-square towards Theseus. Then go to 5.
5.  Move complete.

I'm trying to translate this logic into AGS.  Here's what I'm thinking.  Every time the player moves, the following operation is called twice, because the minotaur moves twice as fast as the player --

Code: ags

  float dx = IntToFloat(player.x - cMinotaur.x);
  float dy = IntToFloat(player.y - cMinotaur.y);
  int distance = FloatToInt(Maths.Sqrt(dx*dx + dy*dy));  //distance now refers to the ACTUAL distance between the player and the Minotaur
  int z= 10;  // the grids are presumed to be 10 pixels apart

  float horizontalcheckx =   float dx = IntToFloat(player.x - cMinotaur.x+z);
  float horizontalchecky = IntToFloat(player.y - cMinotaur.y);
  int horizontalcheckdistance = FloatToInt(Maths.Sqrt(horizontalcheckx*horizontalcheckx + horizontalchecky*horizontalchecky));

  if (distance > horizontalcheckdistance){cMinotaur.Move(x+z,y);}  // If moving to the right gets you closer, then move to the right.  Now, there should be a check inserted in here to see if the minotaur CAN move to the right without hitting a wall.  I have zero idea how to pull that off, so what I would probably end up doing is making the wall an object and in the event of a colission, have the minotaur go back where he came from....

  else {

  z= -10;  //Now let's check the left.

  float horizontalcheckx =   float dx = IntToFloat(player.x - cMinotaur.x+z);
  float horizontalchecky = IntToFloat(player.y - cMinotaur.y);
  int horizontalcheckdistance = FloatToInt(Maths.Sqrt(horizontalcheckx*horizontalcheckx + 

horizontalchecky*horizontalchecky));

  if (distance > horizontalcheckdistance){cMinotaur.Move(x+z,y);}  // If moving to the left gets you closer, then move to the left.

   }

  else {

  float verticalcheckx =   float dx = IntToFloat(player.x - cMinotaur.x);
  float verticalchecky = IntToFloat(player.y - cMinotaur.y+z);
  int verticalcheckdistance = FloatToInt(Maths.Sqrt(verticalcheckx*verticalcheckx + 

verticalchecky*verticalchecky));
	
  if (distance > verticalcheckdistance){cMinotaur.Move(x,y+z)}  //If moving up gets the minotaur closer, move up.

else {

z=10

  float verticalcheckx =   float dx = IntToFloat(player.x - cMinotaur.x);
  float verticalchecky = IntToFloat(player.y - cMinotaur.y+z);
  int verticalcheckdistance = FloatToInt(Maths.Sqrt(verticalcheckx*verticalcheckx + 

verticalchecky*verticalchecky));

  if (distance > verticalcheckdistance){cMinotaur.Move(x,y+z)}  // if moving down gets the minotaur closer, move down

}
}
}

Does the logic here seem okay to you?  Or am I going about this all wrong?  Is there a better way to achieve the same results?

[Calin Leafshade]

Here is my AGS implementation of A* pathfinding. It's not very optimized but it should be fine for small grids and for learning purposes.
It may not be suitable for your game, it really depends on how you plan to use it.

CalculatePath returns an array of ints. The first one is the number of ints in the array.

The rest represent AGS loop directions. So 0 = down, 1 = left, 2 = right and 3 = up.

The only bit you should need to change is SetNode. This function checks if a tile x,y can be moved to. All you need to do is add something like:

Code: ags

    if (!CanMoveToTile(x,y)) return;

You'll also need to remove alot of stuff that was specific to my game. Stuff like tile type and so on. Most of it can be just stripped out.

That function also checks if a coordinate set is sane, so you'll need to check for that.

Code: ags

struct Node{
  int f;
  int g;
  int h;
  bool open;
  int x;
  int y;
  int parent;
};

enum eDirection { eSouth = 0, eWest = 1, eEast = 2, eNorth = 3 }

Node Nodes[1024];
int nodeCount;

int AbsInt(int val)
{
    if (val < 0) return -val;
    else return val;
}

bool IsInNodes(int x,  int y)
{
  int i ;
  while (i < nodeCount)
  {
    if (Nodes[i].x == x && Nodes[i].y == y) return true;
    i++;
  }
  return false;
}

void SetNode(int index, int x, int y, int f, int g, int h, int parent,  bool IgnoreMask,  int IgnoreChar){
  if (!Map.Sane(x, y)) return;
  int tile = Map.Index(x, y, 0);
  int tileType = tiles[tile];
  if (!TileInfo[tileType].Walkable && !IgnoreMask) return;
  if (IsInNodes(x, y)) return;
  if (chars[tile] > -1 && chars[tile] != IgnoreChar) return;
  
  
  Nodes[index].x = x;
  Nodes[index].y = y;
  Nodes[index].h = h;
  Nodes[index].g = g;
  Nodes[index].f = f;
  Nodes[index].open = true;
  Nodes[index].parent = parent;
  nodeCount ++;
}

int lowestF(){
  int i = 0;
  int bestF = 9999999;
  int bestI = -1;
  while (i < nodeCount){
    //Display("Node i:%d, f:%d",i,  Nodes[i].f);
    if (Nodes[i].open && Nodes[i].f < bestF){
      bestF = Nodes[i].f;
      bestI = i;
    }
    i ++;
  }

  return bestI;
}


// This gets the cost to move from sx, sy to dx, dy. 
int MoveCost(int sX, int sY, int dX, int dY)
{
  return 1; // Just return 1 for now.
  int dI = Map.Index(dX, dY,  0);
  int tileType = tiles[dI];
  return TileInfo[tileType].MoveCost;
}


int[] noloopcheck CalculatePath(int sX, int sY, int dX, int dY,  bool IgnoreMask, int IgnoreChar){

  nodeCount = 0;
  int i = 0;
  int f, g, h;
  Display("Path to %d, %d", dX,  dY);
  while (i < 1024){
    Nodes[i].f = 0;
    Nodes[i].g = 0;
    Nodes[i].h = 0;
    Nodes[i].x = 0;
    Nodes[i].y = 0;
    Nodes[i].open = false;
    Nodes[i].parent = -1;
    i++;
  }
  Nodes[0].x = sX;
  Nodes[0].y = sY;
  nodeCount ++;
  bool done = false;
  i = 0;
  while (!done){
      if (i == -1) return null;
      if (Nodes[i].x == dX && Nodes[i].y == dY) done = true;
      Nodes[i].open = false;
      
      g = MoveCost(Nodes[i].x, Nodes[i].y, Nodes[i].x + 1, Nodes[i].y);
      h = (AbsInt(dX - (Nodes[i].x + 1)) + AbsInt(dY - (Nodes[i].y))) * 10;
      f = g + h;
      SetNode(nodeCount, Nodes[i].x + 1, Nodes[i].y, f, g, h, i,  IgnoreMask, IgnoreChar);
      
      g = MoveCost(Nodes[i].x, Nodes[i].y, Nodes[i].x - 1, Nodes[i].y);
      h = (AbsInt(dX - (Nodes[i].x - 1)) + AbsInt(dY - (Nodes[i].y))) * 10;
      f = g + h;
      SetNode(nodeCount, Nodes[i].x - 1, Nodes[i].y, f, g, h, i,  IgnoreMask, IgnoreChar);
      
      g = MoveCost(Nodes[i].x, Nodes[i].y, Nodes[i].x, Nodes[i].y + 1);
      h = (AbsInt(dX - (Nodes[i].x)) + AbsInt(dY - (Nodes[i].y + 1))) * 10;
      f = g + h;
      SetNode(nodeCount, Nodes[i].x, Nodes[i].y + 1, f, g, h, i,  IgnoreMask, IgnoreChar);
      
      g = MoveCost(Nodes[i].x, Nodes[i].y, Nodes[i].x, Nodes[i].y - 1);
      h = (AbsInt(dX - (Nodes[i].x)) + AbsInt(dY - (Nodes[i].y - 1))) * 10;
      f = g + h;
      SetNode(nodeCount, Nodes[i].x, Nodes[i].y - 1, f, g, h, i,  IgnoreMask, IgnoreChar);
      
      
      if (!done) i = lowestF();
    }
  int destnode = i;  

  int list[100];
   
  int c = 0;
  while (i > 0){ // Count Nodes
    list[c] = i;
    i = Nodes[i].parent;
    c++;
  }
  //Display("Count; %d", c);
  int toReturn[];
  toReturn = new int[c + 1];
  toReturn[0] = c;
  int u = c - 1;
  int lastX = sX;
  int lastY = sY;
  int a = 1;
  while (u >= 0)
  {
    //Display("%d %d to %d %d", lastX,  lastY, Nodes[list[u]].x, Nodes[list[u]].y); 
    if (Nodes[list[u]].x > lastX) toReturn[a] = eEast;
    else if (Nodes[list[u]].x < lastX) toReturn[a] = eWest;
    else if (Nodes[list[u]].y < lastY) toReturn[a] = eNorth;
    else if (Nodes[list[u]].y > lastY) toReturn[a] = eSouth;
    lastX = Nodes[list[u]].x;
    lastY = Nodes[list[u]].y;
    u--;
    a++;
  }
  
   return toReturn;
  
}

[KodiakBehr]

Thanks a lot for this Calin.  I read up as much as I could about A* pathfinding, and tried to understand the code you have provided, but it's beyond me.  I appreciate your taking the time, though.

[xerca]

There are some lines like this:

Code: AGS

float horizontalcheckx =   float dx = IntToFloat(player.x - cMinotaur.x+z);

Can I ask what "float dx =" part is doing there? Does it do something I'm not aware? Does it even work? Why not just

Code: AGS

float horizontalcheckx = IntToFloat(player.x - cMinotaur.x+z);

?

Also you seem to create the variables "horizontalcheckx", "horizontalchecky", "horizontalcheckdistance" and their vertical counterparts twice. It could be better to declare them once in the beginning.
Your if-else statement logic is a bit weird, too. I think you are doing something like this:

Code: AGS

if(){}
else{
if(){}
else{
if(){}
else{
if(){}}}}

You can do this instead:

Code: AGS

if(){}
else if(){}
else if(){}
else{}

It is neater and probably more foolproof.

But it will still make the minotaur walk horizontally first if it is a good idea, even if going vertically is a better idea. Maybe you could compare horizontal and vertical distances before deciding on the path, and select the one that would be closer. Or you could make it random (like if both going left and going down will make you closer, select one of them randomly) without comparing. This is not necessary but kind of a better way.
(By the way I'm no expert, just saying what I think)