Legacy GM DS Grid Based AI [Solved]

[Jack the Person]

I have been working on a procedurally generated dungeon crawler for the last 2 months, it works quite well apart from the AI. The game is based around a DS Grid which the enemies use to navigate by getting the direction to the player and moving to one of the 8 surrounding cells, the only problem is that this sort of AI is not very smart, as in they are not able to navigate around obstacles which also exist within the grid.
I did look into using MP Grids but decided not to as I couldn't figure out how I could get the game to calculate a new path after every cell as well as marking which cell was being moved to.
Anyway here's the coding I've got for the AI, feel free to take it:

Create Event:

///Set Variables

//Dynamic Values | Change on a per Enemy Basis
hitPoints = 13 //Health Points
defence = 0 //Defence
damage = 3 //Attack Damage
moveSpeed = 1.5 //Tiles moved per Second
attackSpeed = 2 //Attacks per Second
critChance = 1 //Critical Attack Chance as a Percentage
critMultiplyer = 10 //Critical Attack Damage Multiplyer
state = "Spawn" //Can be Changed | No Reason to do so Though...
alarm[0] = (irandom((room_speed/2)-1)+1) //Time Until Activation | Random Times should Lighten CPU Usage
image_speed = 0 //Basically for any Idle Animation | In Frame per Second
boss = false //Is the Enemy a Boss?
xp = 3 //How much XP the Player is Rewarded with for Killing this Enemy

//Static Values and Formulae | Doesn't Change Between Enemies | Don't Touch
moveSpeed = room_speed/moveSpeed //Converts Value from Tiles per Second to Pixels per Frame
attackSpeed = room_speed/attackSpeed //Converts Value from Attacks per Second to Frames per Attack
oldPoints = hitPoints //Vital in Damage Detection and Particle Creation
image_speed = image_speed/room_speed //Convert Value from FPS to Frames per CPU Cycle
xMove = 0 //Used in Horizontal Movement Calculation
yMove = 0 //Used in Vertical Movement Calculation
xNext = (x div CellArea) //The Enemy's next x Location on the Grid | Based off xCurrent and xMove
yNext = (y div CellArea) //The Enemy's next y Location on the Grid | Based off yCurrent and yMove
xCurrent = (x div CellArea) //The Enemy's Current x Location on the Grid
yCurrent = (y div CellArea) //The Enemy's Current y Location on the Grid
x = (xCurrent * CellArea) //Horizontal Grid Snapping at Spawn
y = (yCurrent * CellArea) //Vertical Grid Snapping at Spawn
ds_grid_set(global.collisionMap,xCurrent,yCurrent,EnemyTile) //Noting the Enemy's Location on the Collision Grid
attacking = false //Is the Enemy Attacking?
depth = -y //Just for Depth Ordering

Alarm 0:

///Delayed State Changes

if state = "Spawn" {state = "Wait"}

if state = "Moving"
{speed = 0
image_speed = 0
sprite_index = spr_enemyLeechIdle
x = xNext * CellArea
y = yNext * CellArea
xCurrent = (x div CellArea)
yCurrent = (y div CellArea)
xNext = xCurrent
yNext = yCurrent
xMove = 0
yMove = 0
state = "Wait"}

Alarm 1:

///Deal Damage

if state = "Attacking" //Checks the Function wasn't called by Accident
   {if (global.collisionMap[# xCurrent+1, yCurrent] == PlayerTile) //Makes Sure the Player
    or (global.collisionMap[# xCurrent-1, yCurrent] == PlayerTile) //is in a Position to
    or (global.collisionMap[# xCurrent, yCurrent+1] == PlayerTile) //be Attacked
    or (global.collisionMap[# xCurrent, yCurrent-1] == PlayerTile)
       {if random(100) <= critChance //Generates a number between 0 & 100 | If Number is Smaller than critChance a Critical Hit is Made
           {global.playerHealth -= round((damage*critMultiplyer)-((damage*critMultiplyer)*(global.defence * 0.075)/100))} //Critical Hit
        else {global.playerHealth -= round(damage-(damage*(global.defence * 0.075)/100))} //Regular Attack
        alarm[1] = attackSpeed} //Resets the Timer if the Player is Still in a Position to be Attacked
else {sprite_index = spr_enemyLeechIdle image_speed = 0 state = "Wait"}} //If the Player is not in Position then the Cycle is Reset

Step (Where the movement code is located):

///State Actions

depth = -y

if state = "Wait" && instance_exists(obj_player)
    {if (global.collisionMap[# xCurrent+1, yCurrent]) == PlayerTile
     or (global.collisionMap[# xCurrent-1, yCurrent]) == PlayerTile
     or (global.collisionMap[# xCurrent, yCurrent+1]) == PlayerTile
     or (global.collisionMap[# xCurrent, yCurrent-1]) == PlayerTile then state = "Attack"
     else {state = "Move"}}
else if state = "Move" && instance_exists(obj_player)
    {var trueDirection = point_direction(x,y,obj_player.x,obj_player.y)
     var roundDirection = round(trueDirection/45)*45
     
          if roundDirection =   0 {xMove =  1 yMove =  0}
     else if roundDirection =  45 {xMove =  1 yMove = -1}
     else if roundDirection =  90 {xMove =  0 yMove = -1}
     else if roundDirection = 135 {xMove = -1 yMove = -1}
     else if roundDirection = 180 {xMove = -1 yMove =  0}
     else if roundDirection = 225 {xMove = -1 yMove =  1}
     else if roundDirection = 270 {xMove =  0 yMove =  1}
     else if roundDirection = 315 {xMove =  1 yMove =  1}
     else if roundDirection = 360 {xMove =  1 yMove =  0}
     else {state = "Wait" xMove = 0 yMove = 0}
     
     if (global.collisionMap[# (xCurrent + xMove), yCurrent] == FreeTile) {xNext = (xCurrent + xMove)} //Check new x-pos is valid
     if (global.collisionMap[# xCurrent, (yCurrent + yMove)] == FreeTile) {yNext = (yCurrent + yMove)} //Check new y-pos is valid
     if (global.collisionMap[# xNext, yNext] != FreeTile) && irandom(1) = 0 {xNext = xCurrent} else if (global.collisionMap[# xNext, yNext] != FreeTile) {yNext = yCurrent} //Makes sure new pos is correct     
     
          if (global.collisionMap[# (xCurrent + xMove), yCurrent] != FreeTile) && (global.collisionMap[# (xCurrent + xMove), yCurrent+1] == FreeTile) && (global.collisionMap[# xCurrent, yCurrent+1] == FreeTile) {yMove = 1}
     else if (global.collisionMap[# (xCurrent + xMove), yCurrent] != FreeTile) && (global.collisionMap[# (xCurrent + xMove), yCurrent-1] == FreeTile) && (global.collisionMap[# xCurrent, yCurrent-1] == FreeTile) {yMove = -1}
     else if (global.collisionMap[# xCurrent, (yCurrent + yMove)] != FreeTile) && (global.collisionMap[# xCurrent+1, (yCurrent + yMove)] == FreeTile) && (global.collisionMap[# xCurrent+1, yCurrent] == FreeTile) {xMove = 1}
     else if (global.collisionMap[# xCurrent, (yCurrent + yMove)] != FreeTile) && (global.collisionMap[# xCurrent-1, (yCurrent + yMove)] == FreeTile) && (global.collisionMap[# xCurrent-1, yCurrent] == FreeTile) {xMove = -1}
     
     if (global.collisionMap[# xNext, yNext] == FreeTile) && xCurrent != xNext or (global.collisionMap[# xNext, yNext] == FreeTile) && yCurrent != yNext
        {ds_grid_set(global.collisionMap,xNext,yNext,EnemyTile) //Mark New Cell as Occupied
         ds_grid_set(global.collisionMap,xCurrent,yCurrent,FreeTile) //Mark Old Cell as Free
         move_towards_point(xNext*CellArea,yNext*CellArea,CellArea/moveSpeed) //Begin Moving to New Cell
         if xNext != xCurrent && yNext != yCurrent then alarm[0] = sqrt(sqr(moveSpeed)+sqr(moveSpeed)) //Is the player moving straight or diagonally?
         else alarm[0] = moveSpeed //Sets When to Stop Moving
         state = "Moving"}
     else state = "Wait"}
else if state = "Attack" && instance_exists(obj_player)
    {     if (global.collisionMap[# xCurrent+1, yCurrent] == PlayerTile) {sprite_index = spr_enemyLeechBiteR image_speed = (18/room_speed) alarm[1] = attackSpeed state = "Attacking"} //(x/room_speed) produces a speed of x FPS
     else if (global.collisionMap[# xCurrent-1, yCurrent] == PlayerTile) {sprite_index = spr_enemyLeechBiteL image_speed = (18/room_speed) alarm[1] = attackSpeed state = "Attacking"} //Three Bites / Second
     else if (global.collisionMap[# xCurrent, yCurrent+1] == PlayerTile) {sprite_index = spr_enemyLeechBiteD image_speed = (18/room_speed) alarm[1] = attackSpeed state = "Attacking"} //One bite is 9 Frames
     else if (global.collisionMap[# xCurrent, yCurrent-1] == PlayerTile) {sprite_index = spr_enemyLeechBiteU image_speed = (18/room_speed) alarm[1] = attackSpeed state = "Attacking"}
     else {sprite_index = spr_enemyLeechIdle image_speed = 0 state = "Wait"}}

//Manage Health     
if instance_exists(obj_player) {if state != "Move" && state != "Moving" {
if (global.collisionMap[# xCurrent+1, yCurrent] == PlayerTile) && obj_player.attackDirection = "Left" or
   (global.collisionMap[# xCurrent, yCurrent+1] == PlayerTile) && obj_player.attackDirection = "Up" or
   (global.collisionMap[# xCurrent-1, yCurrent] == PlayerTile) && obj_player.attackDirection = "Right" or
   (global.collisionMap[# xCurrent, yCurrent-1] == PlayerTile) && obj_player.attackDirection = "Down"
{if mouse_check_button_pressed(mb_left)
    {hitPoints -= round(global.swordDamage - (global.swordDamage * (defence * 0.075) /100))
     if hitPoints >= 0 audio_play_sound(snd_hit,0.1,false)}}

if hitPoints != oldPoints {event_perform(ev_other,ev_user0)}}}

If you read through all that, I'd just like to point out that the User 0 event is just for particle creation and death detection which makes it irrelevant to the problem.

The collision grid is made up of 4 types of tiles: OccupiedTile, FreeTile, PlayerTile and EnemyTile, the player and enemies can only move around in the free tiles and the player and enemy tiles are just for attacking purposes and other than that act like an occupied tile to all other instances.

Any improvements or replacements to the AI will be highly appreciated. Thank you.

 

[Bingdom]

I think mp_grids will be your best bet.

For when you are moving the tiles you can do something like this
mp_grid_clear_cell to current coords
move tile to new place
mp_grid_add_cell to new coords

 

[Jack the Person]

Yes, I did look into mp_grids but the problem I had with them is that from what I've gathered, they can't be dynamically updated, so the enemy will go to the position of where the player was when the path was created as opposed to where they currently are.
Another problem with the whole mp_grid idea is that the game features doors which mean that in many scenarios the path won't be executed.

While they seem like a good idea, mp_grids simply aren't flexible enough, unless there is a way to move the enemy one cell at a time.
Thanks for the suggestion and quick reply though.

I believe I read about ds grid based AI in a tech blog back in April 2015, however, not much information in terms of coding was given.

 

[Bingdom]

The paths can be updated as the player moves along

Create event

//Initialize path
path = path_add();
spd = CELL_SIZE;
alarm[0] = room_speed;

Do something like this, and put it into an alarm

if instance_exists(OBJ_Player) {
    var xx = (OBJ_Player.x div Cell_Width) * Cell_Width + Cell_Width/2
    var yy = (OBJ_Player.y div Cell_Height) * Cell_Height + Cell_Height/2
    //Now got coords in grid, now check if a path is possible
    if mp_grid_path(grid_path, path, x,y,xx,yy,false) {
        //Move along path
        path_start(path,spd,path_action_stop,false);
    }
}
alarm[0] = room_speed;

As for the 1 cell at a time, you can make the object move for 1 step at the speed of CELL_SIZE, and use path_end();. Then trigger the alarm event again and let it run for 1 step. I haven't tested, but this might be worth a go.

 

[Jack the Person]

I've begun implementing this system which works well for the most part (thanks!) but how do I stop the enemies from walking over each other, or in other words, how do I stop them colliding?

 

[Bingdom]

You can store the original position of the enemy before it moves. When the enemy moves up, and a collision is detected then move back to its original spot.

 

[Jack the Person]

I tried adding that in but...

...this happened. All I really need to do is stop the enemies colliding with each other and the player.
Just got to figure out how...

 

[TimothyAllen]

First off, its really easy to implement your own A* algorithm instead of wasting memory on both paths and an additional data sctructure (used by the mp_ path finding). Its also a good learning experience. But that being said, if you wish to stick with the mp_ path finding then i would suggest using mp_add_cell and mp_clear_cell when moving the player and enemies.

Basically when an enemy is looking to get a new path via mp_grid_path function, you would use mp_clear_cell to clear its current position in the grid. After finding a path, you would use mp_add_cell to mark your destination cell as occupied. (or remark your current cell if you fail to find a path). Same logic for the player. When moving out of a cell, clear the cell and add the cell you are headed to.

 

[Jack the Person]

That's a great idea, thanks! I was already doing this with the player as I know where the player is moving to, but I have no clue how to read paths themselves, so how would I know which tile the enemy is moving to? Currently the enemies calculate an entire path to the player and then stop the path and update it after the time to move 1 cell had passed. I'm sure there's probably a simple solution to reading the paths themselves as mp_grids are involved in the generation of the dungeon itself, linking the rooms by creating paths and sending objects to write the corridors into the grid as opposed to what I'd like to do which is read the paths themselves to speed up the process.

You also mentioned a method of AI pathfinding that doesn't use mp_grids, I'm quite interested how to go about that.

 

[anomalous]

I think you should re-look at how you are doing things.

1. mp_grid_path works fine, its unlikely anything you are doing would be improved in any way by not using it, or rewriting it.

2. You do not need to use path_start, if you do not want your opponents to follow the path you just generated. Instead, use the path functions to get the number of points, then set point 0 as your move target, and use other movement functions/logic to move from current position to that position. You can use potential step, for example. When you are very close to destination point, set the next point as destination point. Until you reach the end or something else. In this way the path is just a guide that you move towards "if you can", etc.

2. Moving to the player is what you told it to do when you drew a path to the player, and use path_start.
Instead, as you move, you can check range to player, and if close enough, stop moving and do shooting/idle, etc. This is your AI code.

3. mp_grid_path accepts obstacle input on the grid. This is best for static objects. I don't think most games use dynamic pathing every step, they use other methods to avoid obstacles as they follow a path. You can regen paths periodically, just don't do it every step.
- most people find moving on top of one another is acceptable as long as they are moving and not bunched up for a while.
You do this by having code that says "If I'm no top of another bad guy, one of us should move this way, the other that way", or set up a priority for enemies, and if my priority is lower than the guy I'm stomping on, I wait until he moves off me, then I move. etc. These are all very game/look/designer dependent. A number of people have ways of doing this.

If you used potential step, it will navigate around each other, but it can do strange loops...depends on game if it looks OK and could be fixed, etc.

Hope that helps. It took me a long time to get moment to look fairly intelligent, pathing is just the first easy step to ensure you can reach the target and you know at least one route that will get you there.

 

[Jack the Person]

I can't thank you enough, my AI is now (almost) perfect and I am very happy with the results, and once again thank you!

 

[TimothyAllen]

1. mp_grid_path works fine, its unlikely anything you are doing would be improved in any way by not using it, or rewriting it.

I think there is great value is writing your own pathfinding.
One it's a good way to improve your skills as a programmer, but I understand some people aren't worried about being a programmer and just want to make games. But secondly, as far as I know, game makers built in path finding only allows for marking cells at 0 or 1. Either you can walk on it or you can't. By doing it yourself you can create areas that are more expensive to move on... Like mud. But again, he may not want anything like this. Pathfinding + steering is good advice.

 

[Jack the Person]

Well what I ended up doing is just using the AI I already had with the DS grid and just used the MP grid path's points to set a destination cell, so I do have total control over the speed of the movement as I am just using the path points given to me by the mp grid to note where I want the enemy to move on the DS grid, so in a way, I suppose it is sort of a custom pathfinding.
Or if that doesn't make any sense, here's the code I changed.

Old Step Code (Move State)

else if state = "Move" && instance_exists(obj_player)
    {var trueDirection = point_direction(x,y,obj_player.x,obj_player.y)
     var roundDirection = round(trueDirection/45)*45
     
          if roundDirection =   0 {xMove =  1 yMove =  0}
     else if roundDirection =  45 {xMove =  1 yMove = -1}
     else if roundDirection =  90 {xMove =  0 yMove = -1}
     else if roundDirection = 135 {xMove = -1 yMove = -1}
     else if roundDirection = 180 {xMove = -1 yMove =  0}
     else if roundDirection = 225 {xMove = -1 yMove =  1}
     else if roundDirection = 270 {xMove =  0 yMove =  1}
     else if roundDirection = 315 {xMove =  1 yMove =  1}
     else if roundDirection = 360 {xMove =  1 yMove =  0}
     else {state = "Wait" xMove = 0 yMove = 0}
     
     if (global.collisionMap[# (xCurrent + xMove), yCurrent] == FreeTile) {xNext = (xCurrent + xMove)} //Check new x-pos is valid
     if (global.collisionMap[# xCurrent, (yCurrent + yMove)] == FreeTile) {yNext = (yCurrent + yMove)} //Check new y-pos is valid
     if (global.collisionMap[# xNext, yNext] != FreeTile) && irandom(1) = 0 {xNext = xCurrent} else if (global.collisionMap[# xNext, yNext] != FreeTile) {yNext = yCurrent} //Makes sure new pos is correct     
     
          if (global.collisionMap[# (xCurrent + xMove), yCurrent] != FreeTile) && (global.collisionMap[# (xCurrent + xMove), yCurrent+1] == FreeTile) && (global.collisionMap[# xCurrent, yCurrent+1] == FreeTile) {yMove = 1}
     else if (global.collisionMap[# (xCurrent + xMove), yCurrent] != FreeTile) && (global.collisionMap[# (xCurrent + xMove), yCurrent-1] == FreeTile) && (global.collisionMap[# xCurrent, yCurrent-1] == FreeTile) {yMove = -1}
     else if (global.collisionMap[# xCurrent, (yCurrent + yMove)] != FreeTile) && (global.collisionMap[# xCurrent+1, (yCurrent + yMove)] == FreeTile) && (global.collisionMap[# xCurrent+1, yCurrent] == FreeTile) {xMove = 1}
     else if (global.collisionMap[# xCurrent, (yCurrent + yMove)] != FreeTile) && (global.collisionMap[# xCurrent-1, (yCurrent + yMove)] == FreeTile) && (global.collisionMap[# xCurrent-1, yCurrent] == FreeTile) {xMove = -1}
     
     if (global.collisionMap[# xNext, yNext] == FreeTile) && xCurrent != xNext or (global.collisionMap[# xNext, yNext] == FreeTile) && yCurrent != yNext
        {ds_grid_set(global.collisionMap,xNext,yNext,EnemyTile) //Mark New Cell as Occupied
         ds_grid_set(global.collisionMap,xCurrent,yCurrent,FreeTile) //Mark Old Cell as Free
         move_towards_point(xNext*CellArea,yNext*CellArea,CellArea/moveSpeed) //Begin Moving to New Cell
         if xNext != xCurrent && yNext != yCurrent then alarm[0] = sqrt(sqr(moveSpeed)+sqr(moveSpeed)) //Is the player moving straight or diagonally?
         else alarm[0] = moveSpeed //Sets When to Stop Moving
         state = "Moving"}
     else state = "Wait"}

New Step Code (Move State) The one that works.

else if state = "Move" && instance_exists(obj_player)
    {if mp_grid_path(global.levelGrid,path,(x div CellArea)*CellArea,(y div CellArea)*CellArea,(obj_player.x div CellArea)*CellArea,(obj_player.y div CellArea)*CellArea,true) {
     
     var trueDirection = point_direction(x,y,path_get_point_x(path,1),path_get_point_y(path,1))
     var roundDirection = round(trueDirection/45)*45
     
          if roundDirection =   0 {xMove =  1 yMove =  0}
     else if roundDirection =  45 {xMove =  1 yMove = -1}
     else if roundDirection =  90 {xMove =  0 yMove = -1}
     else if roundDirection = 135 {xMove = -1 yMove = -1}
     else if roundDirection = 180 {xMove = -1 yMove =  0}
     else if roundDirection = 225 {xMove = -1 yMove =  1}
     else if roundDirection = 270 {xMove =  0 yMove =  1}
     else if roundDirection = 315 {xMove =  1 yMove =  1}
     else if roundDirection = 360 {xMove =  1 yMove =  0}
     else {state = "Wait" xMove = 0 yMove = 0}
     
     if (global.collisionMap[# (xCurrent + xMove), yCurrent] == FreeTile) {xNext = (xCurrent + xMove)} //Check new x-pos is valid
     if (global.collisionMap[# xCurrent, (yCurrent + yMove)] == FreeTile) {yNext = (yCurrent + yMove)} //Check new y-pos is valid
     if (global.collisionMap[# xNext, yNext] != FreeTile) && irandom(1) = 0 {xNext = xCurrent} else if (global.collisionMap[# xNext, yNext] != FreeTile) {yNext = yCurrent} //Makes sure new pos is correct     
     
          if (global.collisionMap[# (xCurrent + xMove), yCurrent] != FreeTile) && (global.collisionMap[# (xCurrent + xMove), yCurrent+1] == FreeTile) && (global.collisionMap[# xCurrent, yCurrent+1] == FreeTile) {yMove = 1}
     else if (global.collisionMap[# (xCurrent + xMove), yCurrent] != FreeTile) && (global.collisionMap[# (xCurrent + xMove), yCurrent-1] == FreeTile) && (global.collisionMap[# xCurrent, yCurrent-1] == FreeTile) {yMove = -1}
     else if (global.collisionMap[# xCurrent, (yCurrent + yMove)] != FreeTile) && (global.collisionMap[# xCurrent+1, (yCurrent + yMove)] == FreeTile) && (global.collisionMap[# xCurrent+1, yCurrent] == FreeTile) {xMove = 1}
     else if (global.collisionMap[# xCurrent, (yCurrent + yMove)] != FreeTile) && (global.collisionMap[# xCurrent-1, (yCurrent + yMove)] == FreeTile) && (global.collisionMap[# xCurrent-1, yCurrent] == FreeTile) {xMove = -1}
     
     if (global.collisionMap[# xNext, yNext] == FreeTile) && xCurrent != xNext or (global.collisionMap[# xNext, yNext] == FreeTile) && yCurrent != yNext
        {ds_grid_set(global.collisionMap,xNext,yNext,EnemyTile) //Mark New Cell as Occupied
         ds_grid_set(global.collisionMap,xCurrent,yCurrent,FreeTile) //Mark Old Cell as Free
         move_towards_point(xNext*CellArea,yNext*CellArea,CellArea/moveSpeed) //Begin Moving to New Cell
         if xNext != xCurrent && yNext != yCurrent then alarm[0] = sqrt(sqr(moveSpeed)+sqr(moveSpeed)) //Is the Enemy Moving Straight or diagonally?
         else alarm[0] = moveSpeed //Sets When to Stop Moving
         state = "Moving"}
     else {state = "Wait"}}
     else {state = "Wait"}}