Jump to content


Photo

Maze Ai


  • Please log in to reply
11 replies to this topic

#1 xx Zeeke

xx Zeeke

    GMC Member

  • New Member
  • 37 posts

Posted 11 April 2011 - 05:28 AM

Okay so, I'm working on this maze game.
The maze is automatically generated at the start of the game, I'm aiming to have one playable character, and three AI characters and the objective is to reach the end of the maze before the AI.
I'm having extraordinary trouble with the AI.
The collision mask of the hedges/walls is 40x40. The grid size is 20x20 so as there is a line between the walls where free ground is.
I need someone to help me figure out how I can get the AI through scripting to wander around the maze, and only when they are near the end do they compute a path using the mp_grid function to get to the goal. It would also be great if they could not go over places they have already been/or realize before they hit a wall, that it is a dead end and turn around. Currently, they (being me and my dog) wander aimlessly- occasionally becoming stuck on a wall, or repeating their previous path in terms of going back to the same position over and over after leaving it.
Help would be greatly appreciated- thank you :)

Posted Image

Edited by xx Zeeke, 11 April 2011 - 05:32 AM.

  • 0

#2 IceMetalPunk

IceMetalPunk

    InfiniteIMPerfection

  • Retired Staff
  • 9314 posts
  • Version:Unknown

Posted 11 April 2011 - 05:36 AM

Are the start and end positions always the same (those in the picture)? If so, it would be easy to custom-tailor an AI for your maze type. If not, you might have to try something like the Wall follower algorithm.

-IMP ;) :)
  • 0

#3 xx Zeeke

xx Zeeke

    GMC Member

  • New Member
  • 37 posts

Posted 11 April 2011 - 05:38 AM

Yeah the start and end positions are always the same, but I don't want them to go directly from one to the other.
  • 0

#4 creativebunch

creativebunch

    The Bunchiest

  • GMC Member
  • 886 posts
  • Version:GM:Studio

Posted 11 April 2011 - 06:05 AM

I'm actually just about to start making a maze AI, what I'm going to do is make the AI drop bread crumbs (either an array or objects) as they walk around the maze, so every time they come to a junction they will check if there are crumbs down one path, and if so they should go down a different one. Not sure how effective it will be but it seems good in my head.
  • 0

#5 IceMetalPunk

IceMetalPunk

    InfiniteIMPerfection

  • Retired Staff
  • 9314 posts
  • Version:Unknown

Posted 11 April 2011 - 06:08 AM

Well, I don't know any maze-solving algorithms that go immediately from start to finish, even if the start and end positions are known ;) . Even GM's own path-finding algorithms do a guess-and-check, but it's done behind the scenes before anything is returned.

If the start and end are the same, then this is very similar to a programming project I had for my C++ course.

First, you'll want to represent the maze as a ds_grid, where 1=free space and 0=wall. So if your grid spaces are 32x32, your grid representation will be room_width/32 by room_height/32.

Next, notice the optimal direction to get from the start to the end is up/left. But we can only move in 90-degree increments. So every time we move, we want to first check if we can move up, and if so, we do. If we can't, then we check left; then down; then right.

Every time we move, our previous position (in the grid, not the room; should be equal to <x div 32, y div 32>) is added to a ds_stack to signify it's just been visited. This allows us to avoid moving back and forth. Every time we move, we also pop the last value off the stack before pushing our previous position; this means we'll never move back to the previous position but can still visit an already-visited square later on if need be.

We continue this until we get out of the maze. Oh, and as long as you have the maze bordered by walls, you won't even have to worry about checking if you're falling off the screen. So assuming you have a ds_grid representation of your maze called "grid", this should do it (in the AI object):

/* CREATE event */
visitedX = ds_stack_create();
visitedY = ds_stack_create();

/* STEP event */

/* See if we can win */
if ((y==ENDING_Y && (x-32==ENDING_X || x+32==ENDING_X)) || (x==ENDING_X && (y-32==ENDING_Y || y+32==ENDING_Y))) {
  /* You've won. Do whatever. */
}

/* Check up */
if (ds_grid_get(grid, x div 32, (y div 32)-1)==1 && ((x div 32)!=ds_stack_top(visitedX) || (y div 32)-1!=ds_stack_top(visitedY))) { /* Make sure there's no wall and this is not the previous space */

  ds_stack_pop(visitedX);
  ds_stack_pop(visitedY); /* Pop the previous value off the stack. */

  ds_stack_push(visitedX, x div 32); /* Add current x to the stack. */
  ds_stack_push(visitedY, y div 32); /* Add current y to the stack. */

  y-=32; /* Move up 1 space */
}
/* Check left */
else if (ds_grid_get(grid, (x div 32)-1, y div 32)==1 && ((x div 32)-1!=ds_stack_top(visitedX) || (y div 32)!=ds_stack_top(visitedY))) { /* Make sure there's no wall and this is not the previous space */

  ds_stack_pop(visitedX);
  ds_stack_pop(visitedY); /* Pop the previous value off the stack. */

  ds_stack_push(visitedX, x div 32); /* Add current x to the stack. */
  ds_stack_push(visitedY, y div 32); /* Add current y to the stack. */

  x-=32; /* Move left 1 space */
}
/* Check down */
else if (ds_grid_get(grid, x div 32, (y div 32)+1)==1 && ((x div 32)!=ds_stack_top(visitedX) || (y div 32)+1!=ds_stack_top(visitedY))) { /* Make sure there's no wall and this is not the previous space */

  ds_stack_pop(visitedX);
  ds_stack_pop(visitedY); /* Pop the previous value off the stack. */

  ds_stack_push(visitedX, x div 32); /* Add current x to the stack. */
  ds_stack_push(visitedY, y div 32); /* Add current y to the stack. */

  y+=32; /* Move down 1 space */
}
/* Check right */
else if (ds_grid_get(grid, (x div 32)+1, y div 32)==1 && ((x div 32)+1!=ds_stack_top(visitedX) || (y div 32)!=ds_stack_top(visitedY))) { /* Make sure there's no wall and this is not the previous space */

  ds_stack_pop(visitedX);
  ds_stack_pop(visitedY); /* Pop the previous value off the stack. */

  ds_stack_push(visitedX, x div 32); /* Add current x to the stack. */
  ds_stack_push(visitedY, y div 32); /* Add current y to the stack. */

  x+=32; /* Move left 1 space */
}

-IMP ;) :)
  • 0

#6 xx Zeeke

xx Zeeke

    GMC Member

  • New Member
  • 37 posts

Posted 11 April 2011 - 06:10 AM

I had thought of that, but then thought of what would happen if they cut off all possible paths and ended up stuck...
EDIT: Omg thank you so much IceMetalPunk I will try it immediately. Thank you !!!! ^^
EDIT: I can't get that to work. What do I have to do for the grid representation ? After reading what you posted I put "ds_grid_create(20,20)" in the create event. My player isn't moving.

Edited by xx Zeeke, 11 April 2011 - 06:29 AM.

  • 0

#7 creativebunch

creativebunch

    The Bunchiest

  • GMC Member
  • 886 posts
  • Version:GM:Studio

Posted 11 April 2011 - 06:39 AM

You need to set up the grid like IMP has:
grid = ds_grid_create(room_width / 32, room_height / 32);
ds_grid_clear(grid, 1);
And when you create a wall you change that position on the grid to being filled (or whatever):
ds_grid_set(grid, x / 32, y / 32, 0);

@IceMetalPunk: While your code is well done, the object will always get stuck at dead ends. If the object goes up a pathway and hits a wall it can't turn around and go back because the previous position is below it.

Edited by creativebunch, 11 April 2011 - 06:41 AM.

  • 0

#8 xx Zeeke

xx Zeeke

    GMC Member

  • New Member
  • 37 posts

Posted 11 April 2011 - 06:44 AM

Oooh thank you. Okay now he is moving really fast...
EDIT: Kay he's going normal speed now, except when the game starts, the character just walks upwards directly off screen...
I changed the "y-=32" parts to their corresponding direction example: y-=32 is direction=90.
Here is the object information:


Information about object: obj_joel

Sprite: spr_joel_right
Solid: false
Visible: true
Depth: 0
Persistent: false
Parent: <no parent>
Mask: <same as sprite>

Create Event:
execute code:

image_speed = 0.7

global.grid = ds_grid_create(room_width / 20, room_height / 20);
ds_grid_clear(grid, 1);

/* CREATE event */
visitedX = ds_stack_create();
visitedY = ds_stack_create();


Alarm Event for alarm 0:
execute code:

//Old method of movement

directory_create[3]:=place_free(x,y+30);
dir[2]:=place_free(x-30,y);
dir[1]:=place_free(x,y-30);
dir[0]:=place_free(x+30,y);
move:=0;
direc:=direction;
for(i:=0; i<360; i+=90)
{
if i!=(direction+180)mod(360) and dir[i/90] then
{
if floor(random(move+1))=0 then
{
direc:=i;
}
move+=1;
}
}
direction:=direc;
if move=0 then
{
direction:=(direction+180)mod(360);
}
alarm[0]:=8;
speed:=4;


Step Event:
execute code:

/* STEP event */

/* See if we can win */
if ((y==ENDING_Y && (x-20==ENDING_X || x+20==ENDING_X)) || (x==ENDING_X && (y-20==ENDING_Y || y+20==ENDING_Y))) {
/* You've won. Do whatever. */
}

/* Check up */
if (ds_grid_get(grid, x div 20, (y div 20)-1)==1 && ((x div 20)!=ds_stack_top(visitedX) || (y div 20)-1!=ds_stack_top(visitedY))) { /* Make sure there's no wall and this is not the previous space */

ds_stack_pop(visitedX);
ds_stack_pop(visitedY); /* Pop the previous value off the stack. */

ds_stack_push(visitedX, x div 20); /* Add current x to the stack. */
ds_stack_push(visitedY, y div 20); /* Add current y to the stack. */

direction=90; speed = 4 /* Move up 1 space */
}
/* Check left */
else if (ds_grid_get(grid, (x div 20)-1, y div 20)==1 && ((x div 20)-1!=ds_stack_top(visitedX) || (y div 20)!=ds_stack_top(visitedY))) { /* Make sure there's no wall and this is not the previous space */

ds_stack_pop(visitedX);
ds_stack_pop(visitedY); /* Pop the previous value off the stack. */

ds_stack_push(visitedX, x div 20); /* Add current x to the stack. */
ds_stack_push(visitedY, y div 20); /* Add current y to the stack. */

direction=180; speed = 4; /* Move left 1 space */
}
/* Check down */
else if (ds_grid_get(grid, x div 20, (y div 20)+1)==1 && ((x div 20)!=ds_stack_top(visitedX) || (y div 20)+1!=ds_stack_top(visitedY))) { /* Make sure there's no wall and this is not the previous space */

ds_stack_pop(visitedX);
ds_stack_pop(visitedY); /* Pop the previous value off the stack. */

ds_stack_push(visitedX, x div 20); /* Add current x to the stack. */
ds_stack_push(visitedY, y div 20); /* Add current y to the stack. */

direction=270; speed = 4; /* Move down 1 space */
}
/* Check right */
else if (ds_grid_get(grid, (x div 20)+1, y div 20)==1 && ((x div 20)+1!=ds_stack_top(visitedX) || (y div 20)!=ds_stack_top(visitedY))) { /* Make sure there's no wall and this is not the previous space */

ds_stack_pop(visitedX);
ds_stack_pop(visitedY); /* Pop the previous value off the stack. */

ds_stack_push(visitedX, x div 20); /* Add current x to the stack. */
ds_stack_push(visitedY, y div 20); /* Add current y to the stack. */

direction=0; speed = 4; /* Move left 1 space */
}

set variable depth to -y

Begin Step Event:
execute code:

if direction = 0
{
sprite_index = spr_joel_right
image_speed = 0.7
}
if direction = 90
{
sprite_index = spr_joel_up
image_speed = 0.7
}
if direction = 180
{
sprite_index = spr_joel_left
image_speed = 0.7
}
if direction = 270
{
sprite_index = spr_joel_down
image_speed = 0.7
}
else
exit

Edited by xx Zeeke, 11 April 2011 - 07:02 AM.

  • 0

#9 IceMetalPunk

IceMetalPunk

    InfiniteIMPerfection

  • Retired Staff
  • 9314 posts
  • Version:Unknown

Posted 11 April 2011 - 07:02 AM

@IceMetalPunk: While your code is well done, the object will always get stuck at dead ends. If the object goes up a pathway and hits a wall it can't turn around and go back because the previous position is below it.

Huh. That's true... let's see if I can remember how we fixed it in my class...

I think it should work if you add this to the end of my original code:

else {
  ds_stack_pop(visitedX);
  ds_stack_pop(visitedY);
  ds_grid_set(grid, (x div 32), (y div 32), -1);
}

What that will do is, if it tries to move in every possible direction and can't because the previous position is in the way, it'll remove the previous position from the visited stack and mark the current position as "-1" (in this case, that represents a "dead end"). That should fix it.

And if you want it to move more slowly, instead of putting it in the STEP event, you can put it in an alarm event that's set to 1 in the CREATE event and then reset to some value (like room_speed for 1 second) at the end of the code.

-IMP ;) :)

*EDIT* I still don't see anywhere where you're setting up the grid. You need to clear it to 1, then put 0's wherever there are walls, like so:

ds_grid_clear(grid, 1);
with (wall_object) {
  ds_grid_set(other.grid, x div 20, y div 20, 0);
}

Also, if you use global.grid instead of just grid, you need to change that everywhere in the code to keep it consistent. And lastly, if your grid size is 20x20 instead of 32x32, you'll also need to change the 32's to 20's.

-IMP ;) :)

Edited by IceMetalPunk, 11 April 2011 - 07:06 AM.

  • 0

#10 xx Zeeke

xx Zeeke

    GMC Member

  • New Member
  • 37 posts

Posted 11 April 2011 - 07:06 AM

-puts that in- okay thanks :) I still can't get this to work, I have no idea what to do so I'll upload the .gmk file for any one of you to take a look at- I'm obviously not smart enough to get this to work lol.

http://www.upurload....948f9b8a45e.gmk

There you go. If possible could you also get the character "obj_rusty" to work as well?? Thank you.

Edited by xx Zeeke, 11 April 2011 - 07:14 AM.

  • 0

#11 creativebunch

creativebunch

    The Bunchiest

  • GMC Member
  • 886 posts
  • Version:GM:Studio

Posted 11 April 2011 - 09:51 AM

I don't have access to GM 8 Pro right now so I can't test it but after looking through it I think I know what's happening.

Since the walls are being created by other objects, when the joel object runs the with statement the walls aren't there yet so nothing in the grid is being set. An easy way to solve this is by putting the code which is inside the with statement into the create event of the wall object.
  • 0

#12 xx Zeeke

xx Zeeke

    GMC Member

  • New Member
  • 37 posts

Posted 12 April 2011 - 12:03 AM

Oh alright well, I did that- the player still continues to walk upwards and off the screen...
><
  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users