• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Matthewj234

Pathfinding algorithm

7 posts in this topic

So, I have been trying to sort out pathfinding for my game, but it isnt working too well. I have tried A* and it didnt work, so I found this algorithm:

1: Origin is now the current square.
2: select an adjacent square who's still set to 0.
if there's none, goto 5.
3: give the selected square a value of the current square +1.
if the selected square is the target, goto 7
4: push selected square onto a list of unfinished squares. goto 2.
5: shift the first value from the unfinished list, make it the current square.
6: goto 2.
7: Target is now the current square.
8: select an adjacent square.
9: if selected square's value is current square -1, set it to the current square.
if it's not, goto 8.
10:store the position of the current square relative to the selected square
(Nort, East, South, West etc.)
if it's the origin, goto 12 after that.
11:goto 8.
12:return list of directions


And this is my implementation:

[CODE]
public void findPath(Vec2D startPos, Vec2D endPos) {
Vec2D start = startPos;
Vec2D end = endPos;

boolean finished = false;
boolean step2 = true, step5 = false, step7 = false;

while (!finished) {
Vec2D c = start;

// Step 2
while (step2) {
for (int i = 0; i < 4; i++) {
Vec2D dta = dirs[i];
int nx = c.x + dta.x;
int ny = c.y + dta.y;

if (costs[nx][ny] == 0) {
if (costs[nx][ny] != -1) costs[nx][ny] = costs[c.x][c.y] + 1;
}

runs++;

if (runs >= w * h) return;
if (nx == end.x && ny == end.y) {
// Step 7, result found.
step2 = false;
step7 = true;
break;
}

unfinished.push(new Vec2D(nx, ny));
}

if (step2) {
step5 = true;
}

// Step5
if (step5) {
Vec2D us = unfinished.firstElement();
unfinished.remove(0);
c.x = us.x;
c.y = us.y;
}
}

// Step 7 (End case)
c.x = end.x;
c.y = end.y;
if (step7) {

for (int i = 0; i < 4; i++) {
Vec2D dta = dirs[i];
int nx = c.x + dta.x;
int ny = c.y + dta.y;

if (costs[nx][ny] < costs[c.x][c.y]) {
directions.add(i);
path.add(new Vec2D(nx, ny));
c.x = nx;
c.y = ny;
break;
}
}

if (c.x == start.x && c.y == start.y) finished = true;
}
}
}[/CODE]
Sadly, it keeps running in a circle, can anyone offer some guidance as to what I have done wrong in the implementation of it, and possibly show me a correct implementation?
0

Share this post


Link to post
Share on other sites
do you want to create a visual path or just want to find a path? I'm not sure on how you could draw the best path but i do know how to solve a maze with a queue (which is a list, but like a line, where who ever got in line first gets out of the line first, i.e. First-In First-Out). Queues (and stacks) have push (add to the end of queue) and pop (remove the front of the queue) operations

here is psuedocode to seeing a maze is solvable

push the start position onto the queue

while (queue is not empty)
{
pop off the front of the queue, this is the current location
if (current location is the end location) '
done

if (NORTH is not marked)
push to the back of the queue and mark the location in some way
repeat for SOUTH, WEST, EAST
}
1

Share this post


Link to post
Share on other sites
[quote name='arkane7' timestamp='1341866943' post='4957411']
do you want to create a visual path or just want to find a path? I'm not sure on how you could draw the best path but i do know how to solve a maze with a queue (which is a list, but like a line, where who ever got in line first gets out of the line first, i.e. First-In First-Out). Queues (and stacks) have push (add to the end of queue) and pop (remove the front of the queue) operations

here is psuedocode to seeing a maze is solvable

push the start position onto the queue

while (queue is not empty)
{
pop off the front of the queue, this is the current location
if (current location is the end location) '
done

if (NORTH is not marked)
push to the back of the queue and mark the location in some way
repeat for SOUTH, WEST, EAST
}
[/quote]

Thanks, your response just clicked in my head :)
0

Share this post


Link to post
Share on other sites
[quote name='Matthewj234' timestamp='1341768274' post='4956970']
So, I have been trying to sort out pathfinding for my game, but it isnt working too well. I have tried A* and it didnt work, so I found this algorithm:
[/quote]

Well, it isn't A* that doesn't work, it was your algorithm. What was your problem with A*? I assume you saw [url="http://www.policyalmanac.org/games/aStarTutorial.htm"]this link[/url]?
1

Share this post


Link to post
Share on other sites
[quote name='BeerNutts' timestamp='1341891504' post='4957498']
[quote name='Matthewj234' timestamp='1341768274' post='4956970']
So, I have been trying to sort out pathfinding for my game, but it isnt working too well. I have tried A* and it didnt work, so I found this algorithm:
[/quote]

Well, it isn't A* that doesn't work, it was your algorithm. What was your problem with A*? I assume you saw [url="http://www.policyalmanac.org/games/aStarTutorial.htm"]this link[/url]?
[/quote]

Indeed I have thank you. And yes, it was my implementation that didnt work.
1

Share this post


Link to post
Share on other sites
Hello,
My teacher( we're studing programming in the engineering school ) said its really hard to find a way without recursion so I wrote this in C when I was 9th grade; I hope it will help you, its console app:
1. You enter your starting and ending position; X >= 0, X <= 24, Y >=0, Y < 25. Yeah I know its fixed but I was too lazy that day xD
2. FIll in the closed boxes; Places where you can't use to reach the final destination
3. It will print you a 25x25 grid where 5 is your start position, 6 is your destination, 1 is the generated way, 2 are the "locked" boxes, and 0 is the free space where you could walk but u actually didn't

Please don't jungle me for not using const and references ;/

[source lang="cpp"]#include <stdio.h>
#include <math.h>



typedef struct _COORD
{
int x, y;
}COORD;

typedef struct _BOX
{
int info, list;
float g, h;
COORD parent;
}BOX;

COORD bestNode();

void CheckNeighbours(COORD cp);
float magnitute(COORD a, COORD b);
//global vars
BOX grid[25][25]; // main maze
COORD ep; // end postion. ( where u must reach )

void printmaze(int clear)
{
//clear flag -> if 1 then it will clear the grid and set it to 0
//else -> jsut print its current state
int i, z;
for(i = 0; i < 25; i++)
{
for(z = 0; z < 25; z++)
{
if(clear == 1) {
grid[i][z].info = 0;
}
printf("%i", grid[i][z].info);
}
printf("\n");
}
printf("\n");
}

int main()
{
COORD cp, sp; int e; COORD ctemp;
e = 0;
printf("Start point. X: / 0-24 / ");
scanf("%i", &sp.y);
printf("Start point. Y: / 0-24 / ");
scanf("%i", &sp.x);
printf("End point. X: / 0-24 / ");
scanf("%i", &ep.y);
printf("End point. Y: / 0-24 / ");
scanf("%i", &ep.x);
printmaze(1);
//add closed
printf("Add a closed block? Yes = 1, No = everything else: ");
scanf("%i", &e);
while(e == 1)
{
printf("Closed Block. X: / 0-24 / ");
scanf("%i", &cp.y);
printf("Closed Block. Y: / 0-24 / ");
scanf("%i", &cp.x);
grid[cp.x][cp.y].list = 2;
grid[cp.x][cp.y].info = 2; // with 2 I've marked the closed postions where u can't go
printf("Add a closed block? Yes = 1, No = everything else: ");
scanf("%i", &e);
}
grid[sp.x][sp.y].info = 5; // start point on the grid
grid[ep.x][ep.y].info = 6; // end point on the grid
printf("\n");
// find best way
cp.x = sp.x;
cp.y = sp.y;
//add to open list;
grid[cp.x][cp.y].list = 1;
grid[cp.x][cp.y].g = 0;
grid[cp.x][cp.y].h = magnitute(cp, ep);
while(!(cp.x == ep.x && cp.y == ep.y)) // while we have not reached the target
{// current postion.x == end postion.x ...

//check best node from open list;
cp = bestNode();
printf("checking %i-%i \n", cp.x, cp.y);
//check out neighbours;
if(cp.x == -25000 || cp.y == -25000) // my grid is fix sized from 0-24 so I use -25000 as a flag
{
printf("There is no way.");
cp.x = ep.x;
cp.y = ep.y;
}else{
CheckNeighbours(cp);
grid[cp.x][cp.y].list = 2; // closed list
}

}

while(!(cp.x == sp.x && cp.y == sp.y))
{
cp = grid[cp.x][cp.y].parent;
grid[cp.x][cp.y].info = 1;
if(cp.x == sp.x && cp.y == sp.y)
grid[cp.x][cp.y].info = 5;
}

printf("\n");
printmaze(2);
printf("End. \n");
scanf("%i", &e);


return 0;
}



void CheckNeighbours(COORD cp)
{
int i, z;
COORD ctemp;
for(i = -1; i < 2; i++)
{

for(z = -1; z < 2; z++)
{
//check if alive;
if(cp.x + i >= 0 && cp.x + i < 25 && cp.y + z >= 0 && cp.y + z < 25)
{
if(!(i == 0 && z == 0))
{
if(grid[cp.x + i][cp.y + z].list != 1 && grid[cp.x + i][cp.y + z].list != 2)
{ //if open list or closed
grid[cp.x + i][cp.y + z].list = 1;
grid[cp.x + i][cp.y + z].parent.x = cp.x;
grid[cp.x + i][cp.y + z].parent.y = cp.y;


//record h value
ctemp.x = cp.x + i;
ctemp.y = cp.y + z;
grid[cp.x + i][cp.y + z].h = magnitute(ctemp, ep);
grid[cp.x + i][cp.y + z].g = magnitute(ctemp, cp) + grid[cp.x][cp.y].g;
printf("new neighbour: %i - %i \n", cp.x + i, cp.y + z);
}else if(grid[cp.x + i][cp.y + z].list == 1)
{
ctemp.x = cp.x + i;
ctemp.y = cp.y + z;
if( grid[cp.x + i][cp.y + z].g > grid[cp.x][cp.y].g + magnitute(cp, ctemp))
{
grid[cp.x + i][cp.y + z].parent = cp;
grid[cp.x + i][cp.y + z].g = magnitute(ctemp, cp) + grid[cp.x][cp.y].g;
}
}
} // end if mid
} // end if alive
} // end for z
}
return;
}

COORD bestNode()
{
int i, z;
int bestf = -25000;
int a = 0;
COORD bestNode;
for(i = 0; i < 25; i++)
{
for(z = 0; z < 25; z++)
{
if(grid[i][z].list == 1)
{
if(a == 0)
{
a = 1;
bestf = grid[i][z].g + grid[i][z].h;
bestNode.x = i;
bestNode.y = z;
}
else
{
if(bestf > grid[i][z].g + grid[i][z].h)
{
bestf = grid[i][z].g + grid[i][z].h;
bestNode.x = i;
bestNode.y = z;
}
}
}

}
}
if(a == 0)
{
bestNode.x = -25000;
bestNode.y = -25000;
}
return bestNode;
}





float magnitute(COORD a, COORD b)
{
COORD toret; float ab;
if(a.x > b.x)
{
toret.x = a.x - b.x;
}else
{
toret.x = b.x - a.x;
}
if(a.y > b.y)
{
toret.y = a.y - b.y;
}else
{
toret.y = b.y - a.y;
}
ab = toret.x * toret.x + toret.y * toret.y;
ab = sqrt(ab);
return ab;
}[/source]
1

Share this post


Link to post
Share on other sites
[quote name='Nickie' timestamp='1341909230' post='4957550']
Hello,
My teacher( we're studing programming in the engineering school ) said its really hard to find a way without recursion so I wrote this in C when I was 9th grade; I hope it will help you, its console app:
1. You enter your starting and ending position; X >= 0, X <= 24, Y >=0, Y < 25. Yeah I know its fixed but I was too lazy that day xD
2. FIll in the closed boxes; Places where you can't use to reach the final destination
3. It will print you a 25x25 grid where 5 is your start position, 6 is your destination, 1 is the generated way, 2 are the "locked" boxes, and 0 is the free space where you could walk but u actually didn't

Please don't jungle me for not using const and references ;/

[source lang="cpp"]#include <stdio.h>
#include <math.h>



typedef struct _COORD
{
int x, y;
}COORD;

typedef struct _BOX
{
int info, list;
float g, h;
COORD parent;
}BOX;

COORD bestNode();

void CheckNeighbours(COORD cp);
float magnitute(COORD a, COORD b);
//global vars
BOX grid[25][25]; // main maze
COORD ep; // end postion. ( where u must reach )

void printmaze(int clear)
{
//clear flag -> if 1 then it will clear the grid and set it to 0
//else -> jsut print its current state
int i, z;
for(i = 0; i < 25; i++)
{
for(z = 0; z < 25; z++)
{
if(clear == 1) {
grid[i][z].info = 0;
}
printf("%i", grid[i][z].info);
}
printf("\n");
}
printf("\n");
}

int main()
{
COORD cp, sp; int e; COORD ctemp;
e = 0;
printf("Start point. X: / 0-24 / ");
scanf("%i", &sp.y);
printf("Start point. Y: / 0-24 / ");
scanf("%i", &sp.x);
printf("End point. X: / 0-24 / ");
scanf("%i", &ep.y);
printf("End point. Y: / 0-24 / ");
scanf("%i", &ep.x);
printmaze(1);
//add closed
printf("Add a closed block? Yes = 1, No = everything else: ");
scanf("%i", &e);
while(e == 1)
{
printf("Closed Block. X: / 0-24 / ");
scanf("%i", &cp.y);
printf("Closed Block. Y: / 0-24 / ");
scanf("%i", &cp.x);
grid[cp.x][cp.y].list = 2;
grid[cp.x][cp.y].info = 2; // with 2 I've marked the closed postions where u can't go
printf("Add a closed block? Yes = 1, No = everything else: ");
scanf("%i", &e);
}
grid[sp.x][sp.y].info = 5; // start point on the grid
grid[ep.x][ep.y].info = 6; // end point on the grid
printf("\n");
// find best way
cp.x = sp.x;
cp.y = sp.y;
//add to open list;
grid[cp.x][cp.y].list = 1;
grid[cp.x][cp.y].g = 0;
grid[cp.x][cp.y].h = magnitute(cp, ep);
while(!(cp.x == ep.x && cp.y == ep.y)) // while we have not reached the target
{// current postion.x == end postion.x ...

//check best node from open list;
cp = bestNode();
printf("checking %i-%i \n", cp.x, cp.y);
//check out neighbours;
if(cp.x == -25000 || cp.y == -25000) // my grid is fix sized from 0-24 so I use -25000 as a flag
{
printf("There is no way.");
cp.x = ep.x;
cp.y = ep.y;
}else{
CheckNeighbours(cp);
grid[cp.x][cp.y].list = 2; // closed list
}

}

while(!(cp.x == sp.x && cp.y == sp.y))
{
cp = grid[cp.x][cp.y].parent;
grid[cp.x][cp.y].info = 1;
if(cp.x == sp.x && cp.y == sp.y)
grid[cp.x][cp.y].info = 5;
}

printf("\n");
printmaze(2);
printf("End. \n");
scanf("%i", &e);


return 0;
}



void CheckNeighbours(COORD cp)
{
int i, z;
COORD ctemp;
for(i = -1; i < 2; i++)
{

for(z = -1; z < 2; z++)
{
//check if alive;
if(cp.x + i >= 0 && cp.x + i < 25 && cp.y + z >= 0 && cp.y + z < 25)
{
if(!(i == 0 && z == 0))
{
if(grid[cp.x + i][cp.y + z].list != 1 && grid[cp.x + i][cp.y + z].list != 2)
{ //if open list or closed
grid[cp.x + i][cp.y + z].list = 1;
grid[cp.x + i][cp.y + z].parent.x = cp.x;
grid[cp.x + i][cp.y + z].parent.y = cp.y;


//record h value
ctemp.x = cp.x + i;
ctemp.y = cp.y + z;
grid[cp.x + i][cp.y + z].h = magnitute(ctemp, ep);
grid[cp.x + i][cp.y + z].g = magnitute(ctemp, cp) + grid[cp.x][cp.y].g;
printf("new neighbour: %i - %i \n", cp.x + i, cp.y + z);
}else if(grid[cp.x + i][cp.y + z].list == 1)
{
ctemp.x = cp.x + i;
ctemp.y = cp.y + z;
if( grid[cp.x + i][cp.y + z].g > grid[cp.x][cp.y].g + magnitute(cp, ctemp))
{
grid[cp.x + i][cp.y + z].parent = cp;
grid[cp.x + i][cp.y + z].g = magnitute(ctemp, cp) + grid[cp.x][cp.y].g;
}
}
} // end if mid
} // end if alive
} // end for z
}
return;
}

COORD bestNode()
{
int i, z;
int bestf = -25000;
int a = 0;
COORD bestNode;
for(i = 0; i < 25; i++)
{
for(z = 0; z < 25; z++)
{
if(grid[i][z].list == 1)
{
if(a == 0)
{
a = 1;
bestf = grid[i][z].g + grid[i][z].h;
bestNode.x = i;
bestNode.y = z;
}
else
{
if(bestf > grid[i][z].g + grid[i][z].h)
{
bestf = grid[i][z].g + grid[i][z].h;
bestNode.x = i;
bestNode.y = z;
}
}
}

}
}
if(a == 0)
{
bestNode.x = -25000;
bestNode.y = -25000;
}
return bestNode;
}





float magnitute(COORD a, COORD b)
{
COORD toret; float ab;
if(a.x > b.x)
{
toret.x = a.x - b.x;
}else
{
toret.x = b.x - a.x;
}
if(a.y > b.y)
{
toret.y = a.y - b.y;
}else
{
toret.y = b.y - a.y;
}
ab = toret.x * toret.x + toret.y * toret.y;
ab = sqrt(ab);
return ab;
}[/source]
[/quote]

Thanks, this was really helpful, showing different ways of achieving the same thing. :)
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0