Jump to content


Photo

A*algorithm Path-finding Actions


  • Please log in to reply
16 replies to this topic

#1 Airslide

Airslide

    GMC Member

  • New Member
  • 44 posts

Posted 27 June 2007 - 10:11 PM

Many of you probably already use Game Maker's built in A*algorithm via scripting. This extension adds actions for its use (simplified). It uses a single grid (for simplicity), has some neat new functions, handles the creation/deletion of paths, has 11 actions and nice icons to top it off.

For those of you who don't know what it is, it is the best path finding system in Game Maker and used by lots of professional games. The included example shows just how effective it is. Provided their destination is valid (ex: not in an obstacle) there is an extremely good chance of getting there. Very good for top-down games with enemies following you or needing to get to another destination somehow.

A MUST for any top-down action game.

Download Link:
Posted Image

Help Document (Copied & Pasted):

A* Motion Planning
Game Maker Extension
By Airslide

Introduction
This extension for Game Maker 7 adds actions to the object action library that use Game Maker's built in A* algorithm, normally accessed via scripting. This extension will automaticly handle the creation/deletion of paths (required to use the system), uses a single global grid (for simplicity), and adds a few easy to use functions such as filling a square area with a grid. More info on this system is inside the Game Maker help. Not all of Game Maker's functions for this motion planning system are available, however these may be added in with a later version.

If you script with Game Maker, you may find these actions somewhat redundant. Via scripting you'll have more control over these commands. These actions are aimed towards users who are new to Game Maker, who cannot script well, or would prefer and easier alternative to scripting.

Please check the included example to see the power of this motion planning and check out the objects to see just how easy it is to use with this extension.

Actions
This Game Maker Extension provides 11 new actions for use in objects or timelines. Each one contains its own unique icon. Relative

Setup Motion Planning Grid - Will allow you to setup a motion planning grid. Includes arguments for x & y position, horizontal cells, vertical cells, cell size x & y. Make sure you call this command (or the next) before using any of the other commands (except setup object for paths) or the game may crash.

Setup Motion Planning Grid (Fill Square) - Will allow you to setup a motion planning grid that fills a square. x & y (1,2) values work just like drawing a rectangle. Then fill in the cell size (x,y sizes are not seperate for this action). For example, you could place the x & y (1) values at 0,0, and x & y (2) values at room_width,room_height, and a cell size of 32 (for example) to fill the entire room. Note: The fill may not be exact depending on the size of the rectangle and size of cells.

Destroy Motion Planning Grid - Deletes the motion planning grid. The motion planning grid must exist.

Add All Instances to Grid - Adds all the instances in the room to the grid. This may not be ideal for most games.

Add All Instances of Object Type to Grid - All all the instances of the specified object type to the grid.

Add Object to Grid - Adds the current instance to the grid.

Setup Objects for Paths - Setups the object for the path system (defines local variables used by the extension). Must be called in create event.

Find a Path to Position - Finds a valid path to a position. If the path is inside an obstacle (object on grid) no path will be created.

Stop the Motion Path - Stops the current motion path. This may seem redudant, as the normal path stopping action will work, but this gives you the option to remove the last used path from memory (if it exists).

If the Instance is Stuck - Returns true if the instance isn't moving (stuck). This usually only happens if the destination is inside an obstacle on the grid.

Draw Grid Cells - Draws the grid cells. Should be used for debuging only. Blocked cells are in red, clear cells are green.


Remember to give credit to Airslide!

Edited by Airslide, 21 July 2007 - 12:56 PM.

  • 0

#2 IamCalle

IamCalle

    GMC Member

  • GMC Member
  • 444 posts

Posted 28 June 2007 - 12:53 AM

Ah yes! -If was hoping an extention like that would come, and it did! =)

-Indeed, that is a must for any top-down game (probably 3D too). -It will be very useful when making bots. :huh:
  • 0

#3 Airslide

Airslide

    GMC Member

  • New Member
  • 44 posts

Posted 28 June 2007 - 12:26 PM

Glad you like it :D

I may add some more commands later. If Instance is Stuck will be changed to If Instance is <Not> Moving, and I'll add a new If Instance is Stuck that actually checks for a collision.

Also, for anyone interested:

global.motionplanninglib_grid is the variable containing the grid ID.

<local> motionplanninglib_path is the variable for an instance (must be setup first) where the path is stored.

More advanced users can use those vars to access that data or use Game Maker's commands and have more control over what is going on.
  • 0

#4 IamCalle

IamCalle

    GMC Member

  • GMC Member
  • 444 posts

Posted 28 June 2007 - 10:33 PM

Hm, that sounds nice. :D
  • 0

#5 IceWind91

IceWind91

    GMC Member

  • GMC Member
  • 493 posts

Posted 01 July 2007 - 12:17 AM

This is very nice, and incredibly useful! There is one problem that I found, though. I have a parent object, which specifies everything that is solid. Unfortunately, the objects that need to move using the motion planning (units for an RTS) have this parent (so that they keep their distance from each other), meaning they don't move, since the grid is considered to be occupied at the position they're standing at. Maybe you could add an option to the "add instances to grid" functions which will exclude the instance that called it, similar to the "notme" argument in collision_box, collision_line, and the other collision functions.

I'll try to find a workaround for now, but I think adding that would save people a lot of time. Very nice extension, and I think this will help me a lot! Thanks!
  • 0

#6 revolutiongames2004

revolutiongames2004

    GMC Member

  • New Member
  • 54 posts

Posted 01 July 2007 - 01:07 AM

the link is broken
  • 0

#7 Airslide

Airslide

    GMC Member

  • New Member
  • 44 posts

Posted 01 July 2007 - 12:57 PM

Works just fine for me. You have to wait a moment though.

EDIT: Oops, didn't see IceWind's post...anyway, I think I sorta get what your saying. There are ways to occupy & clear cells in GM, so I'll look into it. So you want it to basicly ignore the tile it is currently on (since it shouldn't be on an occupied on in the first place)? If I figure something out expect an update soon.

Edited by Airslide, 01 July 2007 - 09:28 PM.

  • 0

#8 Airslide

Airslide

    GMC Member

  • New Member
  • 44 posts

Posted 01 July 2007 - 10:50 PM

This should be worthy of a double post...

Version 1.1 BETA is now available.

Download: Link

Please give me feedback, and if you can get the new grid updating system to work right (I don't have much time to test at the moment)

Also, while you must uninstall V1.0 before installing this to avoid possible conflicts, it DOES use the same library, so you will not have to re-drag n'drop.

From the included TXT file:
Version 1.1 BETA

First off - before installing this into GM, please uninstall V1.0! They are not compatible and it will not overwrite due to extension changes (this will not happen again in future versions).

Some new commands have been added and two previous commands have been modified. "If Instance is Stuck" has been changed to "If Instance is Moving" (check the NOT box to tell if it isn't). A new "If Instance is Stuck" has been added that checks for an actual collision with solid objects. "If a Path Could Not Be Made" has been added, which checks to see if the path couldn't be created and returns true if so.

The command to calculate a path has a new parameter, "update grid". This will remove/add tiles that the object was on. THIS IS NOT YET SUPPORTED. If you get it to work well, your probably lucky.

Also, "Update Grid Collision" (or a name to that effect :D ) has been added, which will also remove/add tiles that the object was on and is to be used in every step. Again, not yet supported, and may have issues/not work well with calculating paths.

If you do try the new grid updating system, you may find that nearby solids are removed, so you may want to add them back occasionally (eg. alarm). Also, as objects move they will not recalculate everyone's path, so you should do this when another object comes in range.

The help files will be updated on V1.1 Final or later. The example has been slightly updated to show the new "path failure" command.

-Airslide
  • 0

#9 Sammual

Sammual

    GMC Member

  • New Member
  • 32 posts

Posted 02 July 2007 - 03:21 PM

Quick question, is this setup to work with Hex Grids as well or just square grids?

Dan
  • 0

#10 Airslide

Airslide

    GMC Member

  • New Member
  • 44 posts

Posted 02 July 2007 - 04:34 PM

Only square grids I believe, I'll double check but I don't thing GM has anything for hexagonal grids for this system.

Also, I will be working more on the 'grid update' system in the coming week so I'd like people to post there findings with the current version.
  • 0

#11 antidote

antidote

    GMC Member

  • New Member
  • 117 posts

Posted 04 July 2007 - 01:13 AM

it shouldn't be to hard to modify the code for hexagonal coords, all you need to do is add some extra coords.
here is a C# example (from Here)
/* doubles x, y, and z hold the initial raw ungridded position */
  double rx, ry, rz;
  int ix, iy, iz, s;

  ix = rx = rint(x);
  iy = ry = rint(y);
  iz = rz = rint(z);
  s = ix + iy + iz;
  if(s) {
    double abs_dx = fabs(rx-x),
           abs_dy = fabs(ry-y), abs_dz = fabs(rz-z);

    if(abs_dx >= abs_dy && abs_dx >= abs_dz) ix -= s; /* abs_dx is max. */
    else if(abs_dy >= abs_dx && abs_dy >= abs_dz)
      iy -= s; /* abs_dy is max. *.
    else iz-=s;
  }

  /* ix, iy, iz now hold the coordinates of the hex. */
I'm sure it won't be TOO hard to convert that into GML
  • 0

#12 Airslide

Airslide

    GMC Member

  • New Member
  • 44 posts

Posted 04 July 2007 - 03:22 PM

I'm just using Game Maker's built in commands for the system and simplifying the use. So I don't think I could make them hexagonal without writing a DLL.
  • 0

#13 user(TheIrishHandGrenade)

user(TheIrishHandGrenade)

    GMC Member

  • GMC Member
  • 97 posts

Posted 24 June 2009 - 07:57 AM

What are the code equivalents of the D&D actions?
  • 0

#14 Krisando

Krisando

    GMC Member

  • New Member
  • 1351 posts

Posted 15 April 2010 - 02:02 PM

Darn, does not support diagonal collision movements. Do you think this would likely to be added?
  • 0

Posted Image


#15 kaibil

kaibil

    GMC Member

  • GMC Member
  • 119 posts
  • Version:GM8

Posted 08 July 2012 - 07:20 PM

wow this is great, but I am having problems with, when sometime the objects will just get stuck , even when there are no objects around.... can someone help?
  • 0

#16 brennaniscool

brennaniscool

    GMC Member

  • New Member
  • 2 posts
  • Version:Mac

Posted 14 June 2013 - 04:22 AM

both links are broken and I can't find the A* algorithm online


Edited by brennaniscool, 14 June 2013 - 04:23 AM.

  • 0

#17 drt_t1gg3r

drt_t1gg3r

    GMC Member

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

Posted 27 October 2013 - 09:51 PM

both links are broken and I can't find the A* algorithm online

the link took me to the portal where the download is in the upper right side of the title HERE


  • 0

Those who can, ...do. - Those who can't, ... teach, .. or probably took an arrow to the knee.

Avatar created by Stewart. They take avitar requests here