Algorithms: Pathfiding

[Calin Leafshade]

I have a problem thats need solving and it's already pretty well established that my mathematical abilities are poor to say the least so I thought I would outsource this one to people who actually went to school.

Consider the following:

I have a tile height map which is arranged as an array of integers with a range of 0-2 (0 being ground level)

There is a character stood on 1 of these tiles who has a set number of 'movement points'
To travel to an adjacent (non-diagonal) tile of equal or less height to the current tile costs 1 movement point.
To travel to an adjacent (non-diagonal) tile with a height of 1 greater than the current tile costs 2 movement points.
The character cannot travel (directly) to an adjacent tile if the destination tile has a height of 2 greater than the current tile.

My question is how can i determine (by populating a boolean mask array) which tiles a character can move to?

Supplementary question:

If I were to calculate the best route to any of the tiles to which the character can move (as established in question 1) what would be the best way to do that observing all the conditions above.

[Snarky]

Ah, I remember this from a book on game programming I read in the 80s. 

Create a 2D table of the tiles where you store how many movement points the character has left when it has reached that tile. Initialize all values to -1. Populate it iteratively. Also store a list of of tiles the character "moved to" in the last iteration.

So you start with the origin tile in the first iteration, and try to move to all the adjacent tiles, storing how many points you have left when you get there (if it's possible to move to them). Add each of those tiles that you could move to to your list.

In the second iteration, go through the tiles in that list, and for each of them try to move to all the adjacent tiles. (If you have a value populated for any of the adjacent tiles already, only update it if your new "remaining movement points" value is higher than the old value. That can't actually happen with the values you have currently, but if you decide to tweak them it could be possible.) Add those tiles to the list (which you clear between each iteration), and repeat.

The iteration ends when there are no tiles in the list (i.e. no more tiles that can be reached from the character's starting point with that number of movement points). You can use the 2D array as a mask by simply checking whether a certain tile has a value (>=0) set.

I think you can also use the values for pathfinding, by tracing your steps back to the origin. Start with the endpoint, and check which of the adjacent tiles has a value that indicates it was the previous step (its remaining movement points value is higher by the right amount, and your tile is reachable from it). Repeat until you get back to the starting tile. There might be a better way, though.

[Wyz]

like A*? 
Yes, I love that kind of stuff

[TomatoesInTheHead]

Though A* is not really suitable for this problem

Instead of

check which of the adjacent tiles has a value that indicates it was the previous step (its remaining movement points value is higher by the right amount, and your tile is reachable from it).

you could also create a second array to store the predecessors in the path for each tile (values 0-4 as left, right, up, down, and "not set", or something), and update accordingly during the search.
Then you don't have to do the local search during the backtracking, but have to use more memory; might be better, might be worse.

[Calin Leafshade]

Thanks guys although i'm really not a great deal closer than before it seems.

I found this tutorial which explains the process pretty well but i cant think of how to translate this to AGS script without having masses of code.

http://gpwiki.org/index.php/Programming_Turn_Based_Movement

Anyone any ideas?

Specifically, how can i store the open and closed sets efficiently in AGS? I could use an array but it would mean alot of shuffling which doesnt seem that efficient. If this were C# i'd just have a WalkNode struct and have a List and call OpenSet.Add(new WalkNode(x,y)); but there isnt anything like that in AGS.

EDIT: Ok so this is the code i have thus far:

Code: ags

int moveListCount = 0;
int moveList[100];

function addToMoveList(int x,  int y,  int fromTile){
 
 if (!(x > -1 && x < mapWidth && y > -1 && y > mapWidth)) return;
  int newTile = tiles[tileIndex(x, y)];
  if (newTile - tiles[fromTile] > 1) return;
  int newVal = moveMask[fromTile] - (tiles[tileIndex(x, y)] + 1);
  if (newVal < moveMask[tileIndex(x, y)] || newVal < 0) return;
  moveMask[tileIndex(x, y)] = newVal;
  moveList[moveListCount] = tileIndex(x, y);
  moveListCount ++;
  
  
}

function removeFromMoveList(int index){
  int i = index;
  while (i < 99){
    moveList[i] = moveList[i + 1];
    i ++;
  }
  moveListCount --;
}

function setMoveMask(int x,  int y,  int movePoints){
  
  int i = 0;
  while (i < 1024){
    moveMask[i] = -1;
    i++;
  }
  
  i = 0;
  while (i < 100){
    moveList[i] = -1;
    i++;
  }
  int tile = tileIndex(x, y);
  moveMask[tileIndex(x, y)] = movePoints;
  addToMoveList(x - 1, y,  tile);
  addToMoveList(x + 1, y,  tile);
  addToMoveList(x, y - 1,  tile);
  addToMoveList(x, y + 1,  tile);
  
  
  while (moveListCount > 0){
    
    //what goes here?!
  }
  
}

[Snarky]

Well, that explanation looks fundamentally identical to what I described. Your datastructures can be whatever is most convenient for you. Isn't there a module that gives you resizable arrays/vectors in AGS? Just use that. Or just use a fixed array as a circular buffer. If you count up the number of tiles reachable within N moves (where N is the highest number of movement points any unit will ever have), you'll know how big each one needs to be.

[Calin Leafshade]

The stack module involves a lot of resizing of dynamic arrays and so probably is too slow for iteration.

[Calin Leafshade]

Hooray! I have done it.

Here's my code. The algorithm is pretty slow but it seems to work.

Code: ags

int moveListCount = 0;
Point2D *moveList[100];

bool inMoveList(int x,  int y){
  int i = 0;
  while (i < 100){
    if (moveList[i].X == x && moveList[i].Y == y) return true;
    i ++;
  }
  return false;
}

function addToMoveList(int x,  int y,  int fromTile){
 
 if (!(x > -1 && x < mapWidth && y > -1 && y < mapWidth)) return;
 if (inMoveList(x, y)) return;
  int newTile = tiles[tileIndex(x, y)];
  if (newTile - tiles[fromTile] > 1) return;
  
  int newVal = moveMask[fromTile] - (tiles[tileIndex(x, y)] + 1);
  if (newVal < moveMask[tileIndex(x, y)] || newVal < 0) return;
  //Display("%d %d %d %d %d", x,  y,  newVal, moveMask[tileIndex(x, y)], moveMask[fromTile]);
  moveMask[tileIndex(x, y)] = newVal;
  moveList[moveListCount].X = x;
  moveList[moveListCount].Y = y;
  moveListCount ++;
  
  
}

function removeFromMoveList(int index){
  int i = index;
  while (i < 99){
    moveList[i].X = moveList[i + 1].X;
    moveList[i].Y = moveList[i + 1].Y;
    i ++;
  }
  moveListCount --;
}



function setMoveMask(int x,  int y,  int movePoints) {
  
  int i = 0;
  while (i < 1024){
    moveMask[i] = -1;
    i++;
  }
  
  i = 0;
  while (i < 100){
    moveList[i] = Point2D.Create(-1, -1);
    
    i++;
  }
  int tile = tileIndex(x, y);
  moveMask[tile] = movePoints;
  addToMoveList(x - 1, y,  tile);
  addToMoveList(x + 1, y,  tile);
  addToMoveList(x, y - 1,  tile);
  addToMoveList(x, y + 1,  tile);
  
  
  while (moveListCount > 0){
  tile = tileIndex(moveList[0].X, moveList[0].Y);
  addToMoveList(moveList[0].X - 1, moveList[0].Y,  tile);
  addToMoveList(moveList[0].X + 1, moveList[0].Y,  tile);
  addToMoveList(moveList[0].X, moveList[0].Y + 1,  tile);
  addToMoveList(moveList[0].X, moveList[0].Y - 1,  tile);
  removeFromMoveList(0);
  }
  
}

[tzachs]

Well, if you want some performance boost, maybe try to change your last while loop to work on the last item and not on the first. Each time you remove the first item you iterate the entire list again, which will be unnecessary if you use the last item instead.

[beomoud]

moveList.X = moveList[i + 1].X;

This might be a little irrelevant but i had to ask. I knew that you could use an array as a parameter in a function but you would need to include it in the said function's declaration. Here you are using it in a different manner. Can you actually use an array as a variable without accessing it's element? How exactly? Do you only access it's address similar to a pointer?

[Calin Leafshade]

Umm, I am confused.

I copied that code straight from my game and, as you say, it is incorrect.

It should be moveList[ i ].X = moveList[i+1].X.

I dont know where the [ i ] went but that code shouldnt even compile.

EDIT: now i do.

The [ i ] is being caught by bbcode as an italic tag because the old code tags are broken.