next »

[Zack Bell]

I have literally been programming all day. This morning I realized that I was at a point where I could literally program everything that I've ever wanted to make (2d-wise). So I went back through my old notebook of ideas and started doing a bunch of prototypes.

ANYWAY...

I also realized that I haven't ever made an RPG (turn-based). I'm using Game Maker for my prototypes and would like some suggestions when it comes to enemy AI and more specifically, pathfinding.

I need my enemies to move 'x' number of spaces each turn, towards the player (or other party members) while avoiding walls and taking the shortest path.

A* ?
Dijkstra's ?
Another method entirely ?

I don't have much background when it comes to these algorithms, and would like some help, preferably help that could apply to GM.

[Geeze]

Well you can use the same dijkstra map for every enemy, and you don't have to recalculate it if player characters or other goal points don't move. Also it's very useful if you need to avoid players. There was a good talk about advanced use of those in some episode of RL radio, I think it was in interview with Brian (brogue dev)

[bart_the_13th]

Yup, since it was turn based, you can use djikstra/floodfill pathfinding. I also use the simple floodfill for my turnbased strategy game(in flash/AS3)

[Zack Bell]

I was considering floodfill because it sounds like the easiest way to do it for someone who is new at this. Anyone have basic pseudocode for a floodfill pathfinding algorithm?

[Geeze]

Well, this is a java-like implementation.
[][] is a two dimensional array. You can replace with ds_grid or something in GM
Insert needed behavior to all-caps spots

Code:

public int[][] djikstra(Boolean[][] map, List<Point> goals){
  int[][] dmap; //INITIALIZE ARRAY HERE IF NEEDED
  Queue<Point> q;
  Point c;
  List<Point> dirs = {new Point(0,1)...}//All possible directions here (cardinal & diagonal) This is my habit. Always over-OOP etc. to avoid if-clusters
  for (Point p : goals){ //Iterates through list of goalpoints
    if(map[p.x][p.y] == false){
      q.add(p);
      dmap[p.x][p.y] = INT_MAX;//This marks solid places
    }
  }
  while(q.length() > 0){
    c = q.front();
    for(Point p : dirs){
      if(map[p.x][p.y] == false && dmap[c.x][c.y]>= dmap[p.x][p.y]){
        dmap[p.x][p.y] = dmap[c.x][c.y] + 1;
        q.add(p);
      }
      if(map[p.x][p.y] == true{
        dmap[p.x][p.y] = INT_MAX;
      }
    }
  }
  return dmap;
}

I cannot quarantee this will work but I could think it should work. Yeah initializing and stuff is missing there, but it really doesn't matter if you're going to translate it to GML.

[vinheim3]

Made this for someone who requested a node travelling algorithm:

http://www.mediafire.com/?adrw2vtsd4bgw1w

I'd definitely go with floodfill rather than A* for now since it's simpler and does the job fast enough since we're not dealing with huge arrays or lots of computation with these arrays. You may want to swap anything below that mentions floodfill with A* later, since it usually is a lot cleaner and uses less scripts, though I wouldn't know since I haven't tried it.

Despite nodal movement being different from grid-based movement, the algorithm is essentially the same. Floodfill from current spot. Have each node contain memory of which node expanded onto it. Once the target node has been found, create a path that traces backwards to the starting point using this memory, and follow it to the target node. Reset variables used for calculation.

It should be easier for grid-based movement, since rather than listing all of a node's neighbours, you can have the whole grid in an array and check the positions above, below, and to the left and right of you.

You might not like the idea of using paths to follow to the target node since it makes things like jumping up tiles and animations look ugly. This is easily replacable by making your own movement algorithm that is called every time you need to move. It checks if the next node is above/below, animates differently if it is, and changes its x and y differently to make the whole thing look smooth.

Since this is for enemies, you probably have your own algorithm for detecting the possible places you can move to, as well as AI that determines which of those places is most favourable.  In case you don't, it is as simple as following the step above for floodfilling, except the ending goal isn't when you've found a node, but when your enemy can't move anymore. Then use your AI to determine what the target node is¹. Then follow the above steps to follow to it.

¹(a basic one is using pythagoras' theorem to find the distance between you and the nearest unit and using the lowest score as the target node, and picking at random between nodes that have the same lowest score).

EDIT: Later on, when I have access to my home laptop, I'll upload my grid-based game prototypes with AI and pathfinding included.

[Zack Bell]

Thanks guys. I'm going to do a bit of studying before I start to implement anything. Both of you have been a big help though. 

[vinheim3]

Alright, these are my previous attempts at grid-based RPG's. You might want to look at the 2nd one only since it's a cleaner attempt. I tried to make it as simple as possible to understand:

http://www.mediafire.com/?v6gr5cabgpt2gsr

My algorithms take into considerations the height of nodes and the jump values of units so it might over-complicate things a bit. There's also some messy code fixing depth issues, but these attempts were rubbish from the start anyways, since I should have had each tile as a unique object rather than each node.

Also, I take back what I said about A* possibly being better. Most of the time, trying to calculate the possible spaces a unit can move to, its movement range (and later attack ranges and AoE), you'd be using floodfill rather than A*+multiple paths. And you might as well use just one pathfinding algorithm rather than 2 since it means twice the implementation with no noticeable improvement on speed given that this is a 2D game and not, say, Disgaea, which was 3D.

[JasonPickering]

I recently built a algorithm using AS3. it was floodfill and I used this for help.

http://flashgamedojo.com/wiki/index.php?title=Intro_to_Pathfinding

I did mine backwards though I solved from the Player character to the monster. After I reached the end node(my monster) I take the monsters distance value and then move it to the square that is distance-1. it might not be the best, but it works, since I need to pathfind on every turn and it seemed silly to store a Path I would need to replace each turn.

[Zack Bell]

Thanks for all of the replies and info, guys. The isometric view complicated things a bit in the examples, but that's ok.

@Jason: I like the looks of your game and that's one reason that I was going to attempt an RPG, haha. I also read that same tutorial last night when I was looking around! I'll probably attempt something similar.

[pelle]

Floodfill (breadth first seach?) is equivalent to Dijkstras on a map with square tiles that all have equal cost to move through, right?

Also as already pointed out A* is made for 1-to-1-pathfinding, and usually you need 1-to-n anyway, so you're not usually going to need that.

And the three search types are very similar anyway, you can use the same code just swap out a few parts.

My current turn-based game only has Dijkstra's. I have thought of adding A*, but haven't needed it for anything yet, and even if I come up with some case it would be faster for, Dijkstra's without optimizations (in Java!) runs thousands of times per second on a map larger than what I will need, so it might not be worth having two algorithms.

[GZ]

I feel like I'm missing something here, because no one has mentioned the built-in GM system for path finding. In fact, there are multiple!

If you want to implement path finding the quickest way possible, check out the Motion Planning segment of the GM help file. In particular, there is an A* implementation that is fast and easy to work with:

The actual functions for the grid-based approach are as follows:


mp_grid_create(left,top,hcells,vcells,cellwidth,cellheight) This function creates the grid. It returns an index that must be used in all other calls. You can create and maintain multiple grid structures at the same moment. left and top indicate the position of the top-left corner of the grid. hcells and vcells indicate the number of horizontal and vertical cells. Finally cellwidth and cellheight indicate the size of the cells.
mp_grid_destroy(id) Destroys the indicated grid structure and frees its memory. Don't forget to call this if you don't need the structure anymore.
mp_grid_clear_all(id) Mark all cells in the grid to be free.
mp_grid_clear_cell(id,h,v) Clears the indicated cell. Cell 0,0 is the top left cell.
mp_grid_clear_rectangle(id,left,top,right,bottom) Clears all cells that intersect the indicated rectangle (in room coordinates).
mp_grid_add_cell(id,h,v) Marks the indicated cell as being forbidden. Cell 0,0 is the top left cell.
mp_grid_add_rectangle(id,left,top,right,bottom) Marks all cells that intersect the indicated rectangle as being forbidden.
mp_grid_add_instances(id,obj,prec) Marks all cells that intersect an instance of the indicated object as being forbidden. You can also use an individual instance by making obj the id of the instance. Also you can use the keyword all to indicate all instances of all objects. prec indicates whether precise collision checking must be used (will only work if precise checking is enabled for the sprite used by the instance).
mp_grid_path(id,path,xstart,ystart,xgoal,ygoal,allowdiag) Computes a path through the grid. path must indicate an existing path that will be replaced by the computer path. xstart and ystart indicate the start of the path and xgoal and ygoal the goal. allowdiag indicates whether diagonal moves are allowed instead of just horizontal or vertical. The function returns whether it succeeded in finding a path. (Note that the path is independent of the current instance; It is a path through the g rid, not a path for a specific instance.)
mp_grid_draw(id) This function draws the grid with green cells being free and red cells being forbidden. This function is slow and only provided as a debug tool.

It's simple, choose a grid size that suits your graphic tiling, create a grid the size of your playing area, and remove cells that intersect with solid objects (use parent objects to simplify this).

There's only one drawback in my mind and it's something that can't really be managed in a better way because of how GM works. Basically, all paths are returned as an actual path resource. This means you may need to change the way your characters animate or do certain things. Beyond that, it works well and I've yet to have problems using it myself.

[vinheim3]

^ didnt even know it existed  this is better especially with path functions path_get_point_x and path_get_point_y, so you can implement your own movement (isometric, top-down) and animations by checking where the next point is. It's actual only drawback is that it's less flexible when considering movement costs/other things that might be implemented as part of the movement system, but good enough for most 2D top-down, turn-based games.

[Zack Bell]

I have never used the grid functions, haha 

I will definitely spend some time messing around with those tonight, thanks.

 

[Zack Bell]

setting things up with the grid functions was SUPER simple. Creating a grid, setting a path, and moving from one point to the player was very easy. Now I need to limit the number of spaces that each enemy type can move each turn?

[GZ]

There's a number of ways you can do this. Two ideas off the top of my head:

1. Use path_get_length() on the calculated path to get how long it is. Get the distance you want your guy to travel (ie. 128 pixels). Do movement maximum / path_get_length() and don't allow the path_position value to exceed what that number is. Once it does, end the path.

2. Set some variables to count the moment your path starts. Let's say you just assigned the path to your enemy and you only want your enemy to move 128 pixels (on a 32x32 grid, that's 4 spaces). Set a value to 128, then decrease the path speed your guy moves at. So if you assigned the path to move at a speed of 4, reduce 4 from the tracking variable and when it reaches 0, stop the path.

On both of these methods you'll want to snap to the grid after the character is done moving. This is because the movement can exceed it's position by a few pixels on speeds that are not divisors of 32.

I'm sure there are other ways to do this, these are just two ideas.

[Zack Bell]

Your first example seems easy enough and I'm surprised that I couldn't come up with it myself 

I feel so lame when I start using things that I'm not 100% familiar with, haha.

Thanks again, though.