Allegro.cc - Online Community

Allegro.cc Forums » Game Design & Concepts » Flood Fill path finding

This thread is locked; no one can reply to it. rss feed Print
 1   2 
Flood Fill path finding
NiteHackr
Member #2,229
April 2002

Well, I finally got done ripping the old code out of my Deluxe Pacman 2 game and replacing it with totally new pathfinding code and I must say I am quite happy with it. It takes no time at all to execute, all my profiling shows no time spent on it (Code::Blocks profiling, just came up zeros).

I was going to use the A* (A Star) algorithm, which is basically the go to algorithm for pathfinding, but for a game like Pacman, this is better as I only need to run this pathfinding once when the player moves to a new location. if the player is sitting still, this doesn't have to be run, AT ALL! The path finding data can be used by the ghosts no matter where they are on the map without updating the data if the player is still. When you have four ghosts, doing an A* search for each ghost, scares me. ;)

Anyhow, when my function is done running, this is basically the path finding data...

Level 1 starting position path node
#################################################################### 
## 20 19 18 ## 16 17 18 19 20 21 22 21 20 19 18 17 16 ## 18 19 20 ## 
## 19 ## 17 ## 15 ################################ 15 ## 17 ## 19 ## 
## 18 17 16 15 14 15 16 17 18 19 20 19 18 17 16 15 14 15 16 17 18 ## 
######## 15 ## 13 ################################ 13 ## 15 ######## 
      ## 14 ## 12 11 10 ##                ## 10 11 12 ## 14 ##        
######## 13 ######## 09 #################### 09 ######## 13 ######## 
15 14 13 12 ## 10 09 08 09 10 11 12 11 10 09 08 09 10 ## 12 13 14 15 
######## 11 ## 09 ## 07 ######## 13 ######## 07 ## 09 ## 11 ######## 
      ## 10 ## 08 ## 06 ## && && 14 && && ## 06 ## 08 ## 10 ##       
######## 09 ## 07 ## 05 #################### 05 ## 07 ## 09 ######## 
## 10 09 08 07 06 05 04 03 02 01 @@ 01 02 03 04 05 06 07 08 09 10 ## 
## 11 ######## 07 ############## 01 ############## 07 ######## 11 ## 
## 12 ##    ## 08 09 10 ##    ## 02 ##    ## 10 09 08 ##    ## 12 ## 
## 13 ############## 09 ######## 03 ######## 09 ############## 13 ## 
## 14 13 12 11 10 09 08 07 06 05 04 05 06 07 08 09 10 11 12 13 14 ## 
#################################################################### 

This is for level 1 of my Deluxe Pacman 2 game. The && are the ghost's starting positions, the @@ is the pacman start, and the ## are the walls that cannot be passed through.

The way this works is that the player's position is set to zero, then all the surrounding positions are set to 1. Then all those are checked (only the ones that can be moved to) and set to 2 and so on until the map is full. If you look at this data, you can see that all t he ghosts need to do is to move to the map cell with the lowest path value. If you follow a path from them to the player you will see it works. Now pick a random spot anywhere on the map and follow it, you will see no matter where you are, you can find the shortest path to the player. It's quite nice. And the code to do this wasn't all that lengthy... here it is...

#SelectExpand
1// Find the shortest path to mapx, mapy 2void get_path(int path_node[MAPY][MAPX], LEVEL *level, MAP *dest) 3{ 4// Path finding is done thusly: 5// - We first fill in a grid that represents our map with -1s. 6// - Any map locations that have pieces that block movement are set to 999 7// - We then set our destination to zero. 8// - After this we use the floodfill algorithm, which adds +1 to all surrounding nodes of the current node 9// increasing in value until the map is filled, the ghosts can then simply move to the cell with the next 10// lowest value to get the shortest path. This takes into account screen wrap so the ghosts can move around 11// map off the edges if that is shorter. 12 13 STACK_TYPE open_stack; // map locations that need to be checked 14 STACK_TYPE check_stack; // adjacent map locations that need to be checked 15 STACK_ELEMENT cell; // each stack element for the open stack 16 int closed[MAPY][MAPX]; // a map array to show which cells are closed (already checked) 17 int cn = 0; // current node value 18 STACK_ELEMENT check; // used for checking cells 19 20 // fill empty map locations with -1 21 // set map locations that have pieces that block movement to 999 and close them 22 for(int y = 0; y < MAPY; y++) { 23 for(int x = 0; x < MAPX; x++) { 24 // set all path nodes to -1 except lines which block movement 25 if(level->map[y][x].tile == 0 || level->map[y][x].is_pill) { 26 path_node[y][x] = -1; 27 closed[y][x] = 0; 28 } 29 else { 30 path_node[y][x] = 999; 31 closed[y][x] = 1; 32 } 33 } 34 } 35 36 // set destination to zero if it is not a line, otherwise it is an invalid destination. 37 if(path_node[dest->y][dest->x] == -1) { 38 path_node[dest->y][dest->x] = cn; 39 closed[dest->y][dest->x] = 1; 40 } 41 else { 42 path_node[dest->y][dest->x] = 1; // The destination (player location usually) is normally zero, so I set it to 1 43 return; // and return as a simple way to inidcate this is an invalid location. 44 } 45 46 // Initialize our stacks 47 if(!stack_init(&open_stack)) { 48 printf("Error: Failed to initialize open_stack.\n"); 49 exit(1); 50 } 51 if(!stack_init(&check_stack)) { 52 printf("Error: Failed to initialize check_stack.\n"); 53 exit(1); 54 } 55 56 // First we add the destination cell to the open stack so it is checked first 57 stack_push(&open_stack, dest->x, dest->y); 58 59 // Loop while there are open (unchecked) cells on the open_stack. 60 do { 61 stack_pop(&open_stack, &check.x, &check.y); // Read the cell to check. 62 63 // Add the adjacent cells that are not in closed to open (need to be checked), check for wrap as well. 64 cn = path_node[check.y][check.x] + 1; // new cell values for adjacent cells 65 // push cells to be checked onto check stack 66 stack_push(&check_stack, check.x, check.y - 1); // North 67 stack_push(&check_stack, check.x - 1, check.y); // West 68 stack_push(&check_stack, check.x + 1, check.y); // East 69 stack_push(&check_stack, check.x, check.y + 1); // South 70 71 do { // Loop through the check stack 72 stack_pop(&check_stack, &cell.x, &cell.y); // Read the next adjacent cell to check. 73 if(cell.x < 0) cell.x = MAPX - 1; // check for left edge wrap 74 if(cell.x >= MAPX) cell.x = 0; // check for right edge wrap 75 if(cell.y < 0) cell.y = MAPY - 1; // check for top edge wrap 76 if(cell.y >= MAPY) cell.y = 0; // check for bottom edge wrap 77 if(closed[cell.y][cell.x] == 0) { // if this cell is not on the closed list 78 if(path_node[cell.y][cell.x] == -1) { // A cell still be -1 if it cannot be reached. 79 stack_push(&open_stack, cell.x, cell.y); // push it on the open stack to be checked later 80 path_node[cell.y][cell.x] = cn; // set the cell value to the current node (cn) value 81 } 82 } 83 else { // if this cell is on the closed list, check and see if it's current value is greater than the current one. 84 if(path_node[cell.y][cell.x] > cn && path_node[cell.y][cell.x] < 999) // ignore walls 85 path_node[cell.y][cell.x] = cn; // if it is, update this cell's value to the lower one. 86 else if(path_node[cell.y][cell.x] + 1 < cn - 1) { 87 cn = path_node[cell.y][cell.x] + 1; // If it is much lower than the current node, than update the current node 88 path_node[check.y][check.x] = cn; // as this will result in a shorter path 89 } 90 } 91 } while(stack_size(&check_stack) > 0); // keep looping until all surrounding cells are checked 92 closed[check.y][check.x] = 1; // we're done here, set this cell to closed. 93 } while(stack_size(&open_stack) > 0); // keep looping while there are cells need to be checked 94 95 // When we get here, the entire level would be scanned and the shortest path from any location on the map to 96 // the player will be set. No matter where a ghost is, they only need to check the surrounding map cells 97 // and the one with the lowest number (that's what the variable "cn" is above) is the path we need to take 98 // to get to the player the fastest. This takes into account wrapping around the level so if the shortest 99 // path involves travelling off one edge and onto the other, it will take it. This means there is no map design 100 // you can make that the ghosts cannot navigate around. 101 102 // Free up the memory we allocated for our stacks 103 stack_destroy(&open_stack); 104 stack_destroy(&check_stack); 105 106 /* Test code that prints out the resulting node data 107 for(int y = 0; y < MAPY; y++) { 108 for(int x = 0; x < MAPX; x++) { 109 printf("%03i ", path_node[y][x]); 110 } 111 printf("\n"); 112 } 113 */ 114}

A note about this, I am using my stack program I posted in here before (the original one, not the newer one). I altered it for this game so that when you push a value onto it, instead of being added to the top of the stack (the end of it, which is then normally removed first), I add it to the start of the stack (bottom), and then I have to move all the other stack data as a result. This is a little less efficient, and a linked list would have probably been better, but for my uses, there just isn't a whole lot of data that needs to be moved so it doesn't show up on profiling.

As I said, this path finding code is only run when the player moves to a new cell, and when a ghost needs it. Otherwise, I made the path nodes static.

The improvment over my old, ugly code is amazing, so I thought I would share this in case anyone else can use it.

Oh, here is my modified stack code this uses...

vec2_stack.c

#SelectExpand
1/* Dynamic stack for C. 2 * by Neil Roy 3 * January 23, 2016 4 * 5 * This will create a stack (based on the STACK_ELEMENT type) which starts at 1 element 6 * and dynamically resizes itself as needed. When the current stack limit is reached 7 * it will double the size of it and then continue to add to it. 8 * You can pop data from the stack and push to it. 9 * Edit stack.h and change the STACK_ELEMENT to whatever you need. 10 * See stack.h for more details on individual functions. 11 */ 12 13#include <stdio.h> // printf 14#include <stdlib.h> // realloc, free, exit, NULL 15#include <string.h> // memset 16#include "vec2d_stack.h" 17 18 19bool stack_init(STACK_TYPE *stack_ptr) 20{ 21 STACK_ELEMENT *new_data = NULL; 22 stack_ptr->element_size = sizeof(STACK_ELEMENT); 23 24 // Allocate a memory for stack data 25 new_data = (STACK_ELEMENT *)malloc(stack_ptr->element_size); 26 27 if(new_data == NULL) return false; // failed to initialize 28 29 stack_ptr->data = new_data; 30 stack_ptr->max_size = 1; // starts out at 1, increases as needed 31 stack_ptr->top = 0; // IE, empty. 32 33 return true; 34} 35 36 37void stack_destroy(STACK_TYPE *stack_ptr) 38{ 39 // De-allocate memory for stack 40 free(stack_ptr->data); 41 42 stack_ptr->data = NULL; // make certain we point to NULL 43 stack_ptr->max_size = 0; 44 stack_ptr->top = 0; // IE, empty. 45} 46 47 48// custom stack push function specifically for Deluxe Pacman 2 49bool stack_push(STACK_TYPE *stack_ptr, const int x, const int y) 50{ 51 STACK_ELEMENT *new_data = NULL; 52 STACK_ELEMENT element; 53 54 element.y = y; 55 element.x = x; 56 57 // If the stack is full, we will reallocate more memory 58 if(stack_is_full(stack_ptr)) { 59 new_data = (STACK_ELEMENT *)realloc(stack_ptr->data, stack_ptr->max_size * stack_ptr->element_size * 2); // double the size 60 if(new_data == NULL) return false; // reallocation failed 61 stack_ptr->data = new_data; // point to the new data 62 stack_ptr->max_size *= 2; // set the new maximum size 63 } 64 65 // Put new data on top of stack and increment top. 66 // note: stack_ptr->top-1 is the last element, so stack_ptr->top = next one 67 // so we place the next element on stack_ptr->top then increment it. 68 //stack_ptr->data[stack_ptr->top++] = element; 69 70 // Ignore that last comment. ;) Modified this so it puts the new data 71 // at the start of the stack and moves the rest of the data over. 72 // not as efficient, but it works. 73 for(unsigned int i = stack_ptr->top; i > 0; i--) stack_ptr->data[i] = stack_ptr->data[i-1]; 74 stack_ptr->data[0] = element; 75 stack_ptr->top++; 76 77 return true; 78} 79 80 81bool stack_pop(STACK_TYPE *stack_ptr, int *x, int *y) 82{ 83 if(stack_is_empty(stack_ptr)) return false; 84 85 stack_ptr->top--; 86 87 *x = stack_ptr->data[stack_ptr->top].x; 88 *y = stack_ptr->data[stack_ptr->top].y; 89 90 return true; 91} 92 93 94bool stack_is_empty(STACK_TYPE *stack_ptr) 95{ 96 return stack_ptr->top == 0 ? true : false; 97} 98 99 100bool stack_is_full(STACK_TYPE *stack_ptr) 101{ 102 return stack_ptr->top == stack_ptr->max_size ? true : false; 103} 104 105 106bool stack_shrink(STACK_TYPE *stack_ptr) 107{ 108 STACK_ELEMENT *new_data = NULL; 109 110 // If the stack is empty we'll set it to 1 element in size 111 if(stack_is_empty(stack_ptr)) { 112 new_data = (STACK_ELEMENT *)realloc(stack_ptr->data, stack_ptr->element_size); 113 } 114 else { // stack is not empty, set the new size to the last element 115 new_data = (STACK_ELEMENT *)realloc(stack_ptr->data, stack_ptr->top * stack_ptr->element_size); 116 } 117 118 if(new_data != NULL) { 119 stack_ptr->data = new_data; // point to reallocated memory 120 stack_ptr->max_size = stack_ptr->top; // reset maximum size 121 return true; 122 } 123 else return false; 124} 125 126 127size_t stack_size(STACK_TYPE *stack_ptr) 128{ 129 return stack_ptr->top; 130}

vec2_stack.h

#SelectExpand
1#ifndef VEC2D_STACK_H_INCLUDED 2#define VEC2D_STACK_H_INCLUDED 3 4#include <stdbool.h> 5 6// You can alter this so it matches your data requirements, just keep it named STACK_ELEMENT 7typedef struct { 8 int x; 9 int y; 10} STACK_ELEMENT; 11 12// Use this to create your stack object eg: STACK_TYPE stack; 13typedef struct { 14 STACK_ELEMENT *data; 15 size_t element_size; 16 unsigned int max_size; 17 unsigned int top; 18} STACK_TYPE; 19 20bool stack_init(STACK_TYPE *stack_ptr); // Allocates memory for the stack and sets initial stack data 21void stack_destroy(STACK_TYPE *stack_ptr); // De-allocates the stack memory, and resets stack data 22bool stack_push(STACK_TYPE *stack_ptr, const int x, const int y); // Adds the element to the top of the stack 23bool stack_pop(STACK_TYPE *stack_ptr, int *x, int *y); // Removes the last element from the stack 24bool stack_is_empty(STACK_TYPE *stack_ptr); // Returns true if the stack is empty; used by stack_pop() 25bool stack_is_full(STACK_TYPE *stack_ptr); // Returns true if the stack is full; used by stack_push() 26bool stack_shrink(STACK_TYPE *stack_ptr); // Removes unused memory from the stack, shrinking it to fit 27unsigned int stack_size(STACK_TYPE *stack_ptr); // Returns the size of the stack, good for loops 28 29#endif // VEC2D_STACK_H_INCLUDED

---
“The world is a dangerous place to live, not because of the people who are evil, but because of the people who don't do anything about it.” ― Albert Einstein

SiegeLord
Member #7,827
October 2006
avatar

A few minor comments. This algorithm is called Dijkstra's algorithm. For A*, there are actually ways to allow you to reuse the previous computation, but they are somewhat complex... I wouldn't know if they would be better in practice overall.

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

NiteHackr
Member #2,229
April 2002

SiegeLord said:

This algorithm is called Dijkstra's algorithm

Yup, you're right about that. Also called the floodfill by some. The only real difference is that I do not stop at a target, but I fill the entire map so I don't have to call this again if I don't need to.

I can't see A* being faster for this type of map with multiple enemies, it would probably end up being just as fast at best, but the fact that the ghosts in my game are constantly moving means that each one would have to calculate a path out, where as with this, it only needs to be called when the player changes position, and even then, only once. Considering the small size of the map, and the narrow corridors on it, this is the best method. It certainly doesn't show up on my profiling. I played a game recently where the old way I did it got called over 12000 times, where as in the same time with this, it was called less than 200, which was an amazing difference. And when this was called, the execution time was much faster. So... for most purposes and games like this, it is enough.

---
“The world is a dangerous place to live, not because of the people who are evil, but because of the people who don't do anything about it.” ― Albert Einstein

Kris Asick
Member #1,424
July 2001

One of the games I'm working on for my project right now actually requires pathfinding through a maze, but there's some major catches which prevents me from using this sort of algorithm:

1. The maps are about eight times as large as the one you just used as an example.

2. The player is not the only thing which can be tracked as there's two other types of entities in the maze and all types of entities can track all other types of entities. (Meaning each entity would need to create and constantly process its own pathfinding map.)

3. There can be over 100 entities at a time on the map in later levels and each one may need to do pathfinding.

I looked into how Pac Man did its thing and noticed that the algorithms for the ghosts is actually surprisingly simple, so I adapted those algorithms and updated them to be a little more intelligent about the directions being chosen as well as adding support for seeing through tunnels/teleports, then condensed this all down into a scriptable AI system as I have around 30 different AI routines to write and I didn't feel like having to write tons of repeat code for each one. :P

--- Kris Asick (Gemini)
--- http://www.pixelships.com

NiteHackr
Member #2,229
April 2002

Yeah, this is best on smaller maps with a single entity to track and multiple enemies. For larger maps with changing targets, I would absolutely do A*, it is the best in most solutions. It's just this solution is a rare exception.

As for the original pacman, I have that programmed into my game as well! :D Play it on HARD mode and it doesn't use this path finding at all, but instead uses the original methods which were simple, but very effective. I tried my best to duplicate them exactly. I read a great write up on all the intricate details on the original arcane game. Did you know the arcade game had a bug in it's pathfinding code? I corrected their bug in my own game, but that was quite interesting. If I can find the write up I will share it (unless you have already read the same thing I did).

This is a snippit from my game code that does the arcade pacman stuff on hard...

#SelectExpand
1case 2: // AI - dependant on the ghost - like the arcade game's logic 2 switch(i) { 3 case 0: // RED 4 ghost[i].eyes = dir(level, &ghost[i], &target, false); 5 break; 6 case 1: // GRN 7 // set destination to 4 tiles ahead of pacman 8 // dir() will take care of any boundry or invalid destination problems 9 target.x += pacman.dx * 4; 10 target.y += pacman.dy * 4; 11 ghost[i].eyes = dir(level, &ghost[i], &target, false); 12 break; 13 case 2: // CYN 14 // selects a target two tiles in front of pacman and a destination 15 // equal in distance from that tile to the red ghost, but in the 16 // opposite direction. 17 target.x += pacman.dx * 2; 18 target.y += pacman.dy * 2; 19 target.x += (target.x - ghost[0].map.x); 20 target.y += (target.y - ghost[0].map.y); 21 ghost[i].eyes = dir(level, &ghost[i], &target, false); 22 break; 23 case 3: // PUR 24 // Chases Pacman like RED, only runs home when he gets too close 25 if((abs(ghost[i].map.x - target.x) + abs(ghost[i].map.y - target.y)) < 8) 26 target = ghost[i].spawn; 27 ghost[i].eyes = dir(level, &ghost[i], &target, false); 28 break; 29 }

My comments describe their actions, which is the same as the arcade basically. The ghost's eyes always look where they are going, so I set the eyes to look in a direction based on where pacman is. The dir() function is part of he code that decides whether or not to do pathfinding, checks where pacman is etc. I guess I DO use it in this as well, but I was forced to because my game includes a level editor and the normal method the arcade uses won't work with all levels, just their machine's static level. My levels can wrap around in all sorts of different ways so my pathfinding needs to take into account that wrapping; the arcade machine does not, there are some levels in my game that the arcade machine ghosts would be totally lost in because they simply look and say... is pacman up, than move up, is he right? Mve right, with no consideration for paths that wrap around the screen because the original arcade game doesn't need to use them, but I have designed levels where you need to wrap around in order to reach certain sections. Other than using pathfinding for THAT aspect, it works the same in all other respects.

Anyhow, I thought this would be interesting to someone, apparently not. I'll keep my ideas to myself in the future I guess.

---
“The world is a dangerous place to live, not because of the people who are evil, but because of the people who don't do anything about it.” ― Albert Einstein

SiegeLord
Member #7,827
October 2006
avatar

A funny story about this path finding thing. So in one of my LudumDare games I sort of had the same issue, tons of demons trying to find the player. Unfortunately for me, I didn't think to use Dijkstra's algorithm, and instead coded up value iteration (which is a great algorithm if you have stochastic movement). It's a bit simpler to code up (no need for stacks), but you have to go through each tile multiple times (the flood fill analogy also kind of works there). Unfortunately, since my problem had no stochasticity, the algorithm was unnecessarily slow...

Does your game have any AI for the pacman character itself? Might be fun to try to code something up like that.

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

Kris Asick
Member #1,424
July 2001

You know, I just had an interesting thought on this... Every maze is made up of intersections, so perhaps the trick is to scan a maze prior to the start of a level to find all intersections, then each intersection tracks which intersections you need to pass through to reach which intersections the fastest, then when something wants to find something it waits until it reaches an intersection, checks to see which intersection is the closest to the thing you want to track to, then head towards the next intersection in the sequence?

You wouldn't have to store the entire path for each intersection sequence, just the direction of travel. So if a maze has 200 intersections, each intersection stores 199 directions of travel for reaching the other 199 intersections the fastest, which you scan in using a similar algorithm to flood-filling the maze.

...I'm gonna try implementing this with my project, see what happens. ;)

--- Kris Asick (Gemini)
--- http://www.pixelships.com

NiteHackr
Member #2,229
April 2002

You know, I just had an interesting thought on this... Every maze is made up of intersections

I considered doing this. It actually doesn't take long at all. In my own game (Deluxe Pacman 2) actually doesn't scan unless a ghost is at an intersection, and even then, it doesn't scan if the player hasn't moved out of the last cell since the last scan. When I profiled it, I didn't actually scan very much at all. And the time for scanning was too low to register, just zero.

But in my own notes I did think of what you suggest, and that was to just do the intersections, but then... how do you know what is connecting the intersections? :) It's actually quite fast anyhow as you ignore walls and areas you can't move into and you only ever scan paths that are valid, so in a maze like what I have, and the relatively small size, it's plenty fast as it is. But in order to find the path between intersections... you need to do this.

If one of my ghosts is in a cell and they have no intersections, only one direction they can go, and my ghosts cannot go backwards unless they reach a dead end, than there is no need to call the path finding. Only when they have a choice of 2 or 3 possible directions. And of course, at dead ends, they simply reverse directions.

I should try implementing A* and perhaps do a test and see what, if any difference there is in speed. I assume this is faster, but who knows, maybe A* would be? I figured that A* would probably be close to the same speed as this (from some Videos I watched on Youtube where people tested, A* didn't do better in mazes, Floodfill (easier to spell that... the other name, ;) ) was either the same or faster. Certainly easier to implement.

SiegeLord said:

Does your game have any AI for the pacman character itself?

No, but it would be interesting to make a version where you play a ghost instead! :)

Oh, and if you're interested, I found the website where I originally discovered how the Arcade ghosts moved (their AI), this includes the bug in the arcade game that existed, and even a fix for it and the original machine code that produced the bug. Tons of history, basically everything you ever wanted to know plus some. It is a fascinating read. Especially the technical side of things, movement (some bugs with that you could take advantage of, like moving THROUGH a ghost without dying), a limit on the levels for the machine, after level 255 the game bugs out with a screwy level due to the limit in numbers. Tons of stuff, I really enjoyed reading this... (took me some time to find it again as the original site was gone now, but Gamasutra had it reposted so, yay for them!)

http://www.gamasutra.com/view/feature/3938/the_pacman_dossier.php?print=1

---
“The world is a dangerous place to live, not because of the people who are evil, but because of the people who don't do anything about it.” ― Albert Einstein

Kris Asick
Member #1,424
July 2001

I had another interesting thought on this: Flood fill from both the source AND target simultaneously, going back and forth between them doing one iteration each time. The instant one flood fill hits part of another, you have your shortest path. :)

I've decided against doing any super-complex path-finding with my game for a few reasons, the biggest reason being that the state of the level is dynamic, so anything I pre-calculate to cut the calculation times down cannot be relied upon. Another issue is that I have one-way walls in my game which can be passed through in one direction but not the opposite, which creates unusual issues with trying to optimize a path-finding routine. Lastly, time is a big factor as I can't have hundreds of entities all burning memory and CPU time trying to do complex path-finding stuff. :P

I definitely need a stronger algorithm though, as I'm witnessing my AI routinely getting stuck in corners and loops because of how complex the level designs can get, including tunnels which wrap across the edges of the screen and teleports. I'm now thinking of implementing a combination brute-force/range algorithm where the AI will plot out a random selection of paths in each valid direction from its current position up to a certain number of tiles moved and will choose to follow whichever path gets it the closest to its destination. Then, any time an intersection is reached, a few more paths are tested and if any result in an even closer destination coordinate than the current path, it will be followed instead. If any path actually reaches its target though, it will be considered "Perfect" and will be followed all the way to its destination without testing more paths to follow at intersections. If the dynamic nature of a particular level interrupts a path being followed, it will immediately create new paths and choose the best to follow, plus any path which goes through a dangerous level element will be considered "poor" and will have a high probability of simply being ignored during the calculations, though random chance will occasionally allow poor paths to be chosen.

I actually like AI-related algorithms which are not perfect 100% of the time because it makes the AI feel more natural and less predictable. ;)

--- Kris Asick (Gemini)
--- http://www.pixelships.com

Audric
Member #907
January 2001

You know, I just had an interesting thought on this... Every maze is made up of intersections, so perhaps the trick is to scan a maze prior to the start of a level to find all intersections, then each intersection tracks which intersections you need to pass through to reach which intersections the fastest, then when something wants to find something it waits until it reaches an intersection, checks to see which intersection is the closest to the thing you want to track to, then head towards the next intersection in the sequence?

It's an interesting thought, an ever-moving character is always in transit from an intersection (last) and going to another (target).
If ghosts aim for the target, they are very good at anticipating long "straight" movements. If you don't make ghosts revise their goal when the player turns around, it can be a fun way to feint the ghosts - if it's not too easy to abuse.

NiteHackr
Member #2,229
April 2002

The ghosts in my game only check for a path to the player at intersections actually, it's pointless to do it as they cannot turn around 180 degrees unless at a dead end, so I only do a path search if they have more than one direction they can go (a T section or otherwise). And then in the path finding function, it looks to see if the player has moved out of the cell it was in the last time it checked, if not, than it can return with the same path and no need to look again, so it's pretty optimal. After profiling my game, it really doesn't get called a whole lot.

As for Kris' problems, you can still use this idea, it is actually best used with multiple enemies as they can all use the same path data. The more enemies you have the better this becomes and you can take into account 1 way walls. Coming at it from two directions doesn't really make it optimal at all, you will get the same answer no matter what. But coming at this from the player ONLY, and filling in small levels means ALL enemies, no matter where they are on the level can use the same data, so you only ever need to call this once when the player changes his location.

If you check my implementation you will see it is not complicated to implement at all. I have extra code in there for a stack function for C, but if you use C++ you can just use vectors.

---
“The world is a dangerous place to live, not because of the people who are evil, but because of the people who don't do anything about it.” ― Albert Einstein

Kris Asick
Member #1,424
July 2001

Well, there's one small problem: My game has five different types of entities: Players, Cyborgs, Beasts, Shots and FX. Players, Shots and FX don't need to do any pathfinding, but the other two do.

If the player was the only entity being targeted then yes, having a flood fill of some sort would be ideal.

The problem is that the Cyborgs can target the player OR any beasts, which there can be hundreds of at a time in the later levels, while the beasts can target the player OR any cyborgs, which there can only be up to three of but again, there can be up to and over 100 beasts...

Doing that many flood fills on a regular basis on a map that's eight times larger than what you've got going on Neil... I can't see that being good for the framerate. :P

--- Kris Asick (Gemini)
--- http://www.pixelships.com

Bruce Perry
Member #270
April 2000

You could just run a single floodfill from multiple starting points. Of course it does limit the flexibility somewhat: everything will go for the nearest target, regardless of any individual preferences (mmm, I fancy the player more than beasts on this occasion) that you might like to define per enemy. Also the things looking for the nearest target can't be potential targets themselves.

--
Bruce "entheh" Perry [ Web site | DUMB | Set Up Us The Bomb !!! | Balls ]
Programming should be fun. That's why I hate C and C++.
The brxybrytl has you.

NiteHackr
Member #2,229
April 2002

Sounds like you should use different path finding for different enemies then? Perhaps A* for some, flood fill for others. At least that is how I would approach it. They're all fairly simple to implement and easily tweaked to meet your needs.

I was surprised at how easy they really were once I got coding them.

You could also do things the Arcade Pac-Man way, where there is no pathfinding, but just a general direction (depending on how intelligent the enemies are). Take into account their line of sight, really, if they cannot "SEE" their target, how do they know where to go? A more limited path, perhaps to the nearest exits if they cannot "see" any targets... random wandering. Maybe record the last known location of any target they do spot and then head towards the last location then resume searching from there.

Could be a fun project actually, I may try something like this myself.

I even thought about doing something like this in my pacman game, if the ghosts aren't looking at you or see you, than they wander randomly, if they see you, they head to your last known location etc... more realistic. Would allow the player to use obstacles as cover etc.

---
“The world is a dangerous place to live, not because of the people who are evil, but because of the people who don't do anything about it.” ― Albert Einstein

piccolo
Member #3,163
January 2003
avatar

I am doing something like the following for bus sim

Then using Cosine Sin Tan
and a path lookup to navigate

I generate the look-ups for each point once then save it.

I have points only at the Dead ends, intersections and corners
I did not do the full map cause it would take to long to do manually

#SelectExpand
1#################################################################### 2##01 02 ## 05 06 ## 09 10 ## 3## ## ## ################################ ## ## ## 4##04 03 12 07 08 11 ## 5######## ## ################################ ## ######## 6 ## ## ## ## ## ## 7######## ######## #################### ######## ######## 814 13 ## ## 16 15 9######## ## ## ######## ######## ## ## ######## 10 ## ## ## ## && && && && ## ## ## ## 11######## ## ## #################### ## ## ######## 12## @@ ## 13## ######## ############## ############## ######## ## 14## ## ## ## ## ## ## ## ## ## 15## ############## ######## ######## ############## ## 16## ## 17####################################################################

The look up would look as follows.

Point 01 has options of 02,04
Point 03 has options of 02,04 ,12,13
Point 05 has options of 12,06

ect...

for the packman you would have to code teleport points for 15 , 14.

ill Call it the King Piccolo algorithm

wow
-------------------------------
i am who you are not am i

NiteHackr
Member #2,229
April 2002

piccolo said:

I am doing something like the following for bus sim

That works well for just navigating around corners etc... but what I am doing involves the ghosts (enemies) finding the shortest path to the player.

For simple navigation like this, the ghosts check the cell to the right, left, above and below them when they enter a new one. If there is more than one direction they can go, then they will either pick one at random, or they will call the path finding function to find a path to get to the player.

What you have here involves selecting a new direction to travel at intersections, but doesn't help find a paths.

Here's a good example why just simple direction finding like the Arcade version of Pac-Man will simply not work with my game (Deluxe Pacman). The arcade had a fixed map, so it wasn't a problem, but in my game, this type of map is possible, using the arcade method, this is the path the red ghost would travel to reach Pacman and he would end up going in a loop on this map...

################################    ################################
##          ##                                        ##          ##
##    ##    ##    ################################    ##    ##    ##
##                        P ## +----> ##                          ##
##    ##    ##    ######    ## | ##   ##    ######    ##    ##    ##
##          ##              ## +--+   ##              ##          ##
################################  | ################################
##          ##                    G                   ##          ##
##    ##    ##    ##    ########    ########    ##    ##    ##    ##
##    ##    ##    ##    ##    ##    ##    ##    ##    ##    ##    ##
##    ##    ##    ##    ########    ########    ##    ##    ##    ##
##                                                                ##
##    ########    ########    ########    ########    ########    ##
##    ##    ##          ##                ##          ##    ##    ##
##    ##############    ########    ########    ##############    ##
##                            ##    ##                            ##
################################    ################################

This is because the ONLY way to get to the upper half of this map is to go down to the bottom and wrap around. This was a problem I ran into while developing Deluxe Pacman 1, so I was forced to implement a proper path finding algorithm which allowed the ghosts to navigate any map you could throw at it... using the algorithm I already posted here, this is the path the ghost should and will take...

################################  | ################################
##          ##  +-----------------+                   ##          ##
##    ##    ##  | ################################    ##    ##    ##
##              +-------->P ##        ##                          ##
##    ##    ##    ######    ##   ##   ##    ######    ##    ##    ##
##          ##              ##        ##              ##          ##
################################    ################################
##          ##                    G                   ##          ##
##    ##    ##    ##    ########  | ########    ##    ##    ##    ##
##    ##    ##    ##    ##    ##  | ##    ##    ##    ##    ##    ##
##    ##    ##    ##    ########  | ########    ##    ##    ##    ##
##                                +-----+                         ##
##    ########    ########    ########  | ########    ########    ##
##    ##    ##          ##        +-----+ ##          ##    ##    ##
##    ##############    ########  | ########    ##############    ##
##                            ##  | ##                            ##
################################  | ################################

You could also use A* (A-star) to do the path finding, but I doubt it would be any faster on this sort of map. The method I use is very fast, I profiled it and it doesn't even register as taking any time at all (the time is so low it is 0% on the code::blocks profiler).

---
“The world is a dangerous place to live, not because of the people who are evil, but because of the people who don't do anything about it.” ― Albert Einstein

piccolo
Member #3,163
January 2003
avatar

My algorithm would still work and get you to the player on any map however I am not sure how much faster it would be.

I was thinking it would be faster because you are computing fewer points. (n)

to code the bad guys to use the teleport points you would need to modify map generation to note the sections that are generated.

In your example you have 2 sections. Packman is in section 2 and the bad guys is in section 1.

In your recursive find path functions you would has a section look-up that will be done first.

in your example there is only one point in section 1 that will get you to section 2. So you would find the path to that point first then find the rest of the path to Packman.

Edit
I just saw Kris Asick posted the same idea I came up with :(

wow
-------------------------------
i am who you are not am i

NiteHackr
Member #2,229
April 2002

Go ahead, write the code to do that and test it. If you come up with something better, I am all for it. But I think you are glossing over this and missing some points.

For one, the algorithm doesn't "know" what the map looks like, the layout of it or anything. So right away, you have problems. How do you know that is the only spot that reaches the upper half of the map? Now as a human being you can see it right away, but from a programming perspective, it is not quite that easy. You need to scan the entire board. Now perhaps you could scan it when it is first loaded and set up some values for intersections, but again, how do you know the best path to where the pacman is? There's good reasons why algorithms like A* and Floodfill (I can't spell it the other way! ;D) exist.

As for only marking the intersections, well, as I already stated, my game doesn't do a path finding scan UNLESS IT IS AT AN INTERSECTION, so that is utterly pointless and still doesn't explain how the program will be able to find the shortest path! :) I know how to find intersections, that is super simple and there is no need to mark them ahead of time. When my ghosts are travelling east to west, they only need to check 3 directions, the one they are heading in (which is a SINGLE map cell check), the direction to the left, and the one to their right (east to west would mean it would check east, north and south). So that's simple, if it is a dead end, the ghost then turns around. But that doesn't find a path. And you have no way to know which direction leads to the player.

Think this through... show me some code, you'll see that it is not so simple a thing as you suggest. :) Trust me, I already thought about these ideas, but to know which intersections you can move to, you have to scan the spaces BETWEEN THEM (for blockages etc)... so... that's where this algorithm comes in.

Edit: I only created this map as an example, but I liked it enough that I booted up my game editor and made it real. ;D

{"name":"610211","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/b\/8\/b8b6401918468dfb4933c040c7e445e5.png","w":1024,"h":768,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/b\/8\/b8b6401918468dfb4933c040c7e445e5"}610211

---
“The world is a dangerous place to live, not because of the people who are evil, but because of the people who don't do anything about it.” ― Albert Einstein

piccolo
Member #3,163
January 2003
avatar

The path function finds the shortest path the less about of points used is the shortest. I will post when the app is complete for demo curtain parts of the algorithm are used but they are in the data structure for future implementation. ect the part were each point has an array related point ID

wow
-------------------------------
i am who you are not am i

NiteHackr
Member #2,229
April 2002

Wow, I didn't understand a word you said. I look forward to seeing your algorithm. If you have a better way, I am all for it but... I still do not feel you are thinking this through. ;)

---
“The world is a dangerous place to live, not because of the people who are evil, but because of the people who don't do anything about it.” ― Albert Einstein

Kris Asick
Member #1,424
July 2001

Piccolo: The system you have in place is ultimately very rudimentary and will fail under certain map design considerations.

To use an intersection approach you have to do the following:

1. Determine the total number of intersections. (You do not have to scan corners and dead-ends because you can only go one way around a corner and dead-ends you have to double-back from.)

2. Create a 2D matrix of directional values with both dimensions sized based on the number of intersections. (IE: If you have 124 intersections, you need a [124][124] array. This will get HUGE if you stick more than just a single byte into each element so try to keep your directional values confined to a single byte.)

3. Do a pre-calc floodfill for all intersections. As the flood fill progresses, each node in the fill tracks which direction it originally moved in. When it hits an intersection, that mix of source and destination intersections is assigned the appropriate direction, based on which flood fill node hits it.

4. With your entire intersection matrix filled, you now simply input your starting intersection as one index value, your destination intersection as another, and you'll get the appropriate direction of travel from the starting intersection in return. You do need to check this again with each intersection reached of course.

5. Entities using this matrix will only be able to track to a new destination when they are at an intersection, however, if the target is not at an intersection you simply send pulses out from the target in its one or two open directions and choose whichever intersection is hit first by one of these pulses.

I put some more thought into this and I THINK I might be able to get this type of system working with the dynamic nature of my mazes... I think... I'm hoping doing 200 flood-fill ops before each level doesn't slow down the loading times TOO badly, though I could always stick it into an alternate thread as the time between a level being loaded from disk and actively being played is a minimum of about 12 seconds, going through screen transitions and such, which with any luck should be enough time to do that many flood fills, even on a low-end system. ;)

--- Kris Asick (Gemini)
--- http://www.pixelships.com

piccolo
Member #3,163
January 2003
avatar

I would love to see some of those design considerations.
Never had one that failed this would be a first.

Its nothing hard

all I am doing finding a point on a line.

Packman's location is just a point on a line.

the path to packman is just a bunch of connecting lines.

The points of the map represent start and end of a line or the intercept of 2 lines.

You have to have a point for the dead ends because they are part of line packman could be on.

The benefit of my algorithm is that you don't have to compute the points in between the line intercept's. You use look ups that have everything pre computed for you.

earlier I also said that some things would have to be setup for the algorithm.
the map is generated so the point can be configured then.

It would all depend on how the map is generated.

the map I am using is not generated so I have to put in the points manually.
I could make some weird pixel reader config point placer but that's over kill because the points only have to be placed once per map and my map is static.

wow
-------------------------------
i am who you are not am i

Kris Asick
Member #1,424
July 2001

Well, don't forget that a lot of it comes down to what you do with the data you pre-compute.

If you scan through intersections in much the same way you would a flood-fill, it's still going to take a decent chunk of time to find an optimal route. It would be much faster than a straight-up flood fill for sure and definitely suitable when you only have a few entities to worry about in a small map space, however, you'll need to make sure you track the distance between each intersection as well so that your flood fill nodes can track how far they've travelled. The reason being that the distance between all of your intersections is going to vary, so the time to fill through certain sections will go faster the longer the actual distance travelled, thus when one flood fill node hits a target and records its distance, if any nodes still in play have travelled a smaller distance, they need to keep going at least until they exceed the recorded distance, just in case there is a smaller distance which could be travelled.

You won't run into this issue with the method I laid out above, plus you wouldn't have to track as many intersections, plus you wouldn't have to do any flood fills after the initial pre-calcs. That said, if your method is working the way you want it to and isn't burning insane amounts of CPU power, then there's no real reason to change it, right? ;)

--- Kris Asick (Gemini)
--- http://www.pixelships.com

NiteHackr
Member #2,229
April 2002

As I said, when I see some working code I can test from you guys, I will be all for testing it. Anything that can improve things I am all for. But I think your imaginations are getting ahead of reality. It's easy to say "test the space in between" without actually thinking about HOW, from a coding standpoint.

And you will find it awful difficult to precompute anything ahead of time that will work when the player's position, and the enemies can be anywhere on the map, and take into account the wrapping problem I already showed. If you have the same, fixed, unchanging map, like the arcade game had, no problem. In my game it has a level editor where anyone can make a level for it and the game needs to be able to navigate anything you throw at it.

You may be right, and you may be on to something, but I want to see some code, or perhaps type out some pseudo code, which is how I learned to do the A* and floodfill. Here's an image with pseudo code which basically describes how to do a A* for example... if you can show me something like this that makes more sense, I would be interested... (and you may want to save this image as I found it a great way to get a handle on how to do this sort of thing)

{"name":"610216","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/9\/89ad995577a8a1f48520ac379ecbd413.png","w":1280,"h":720,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/9\/89ad995577a8a1f48520ac379ecbd413"}610216

...so far, all I am seeing is a way to determine directions you can go when you reach an intersection, which is not the same as finding the shortest path between the enemy and the player, who could be anywhere on the map. Pre-computing all possible location combinations would be extremely expensive and time consuming, and quite frankly, not necessary given the algorithms like A* and Floodfill (or whatever you choose to call it).

---
“The world is a dangerous place to live, not because of the people who are evil, but because of the people who don't do anything about it.” ― Albert Einstein

piccolo
Member #3,163
January 2003
avatar

I will have something for you to test in a few days however I wont have the auto point mapper because that is not needed in my case however I will code the related points mapper. I my app I am doing that manually however that is key functionality to proving my point for auto generated map shortest path finding using the algorithm.

The compute in my case is not costly because I use sorts to located related points.

once each point has its related point configured. the lookups will work just like Facebook. I connect to you I can see your friends list then each friend has it own friends list until I have the path I want. The path I want gets me to the friend I am looking for using the less amount of friend connection.

wow
-------------------------------
i am who you are not am i

 1   2 


Go to: