Jump to content


Photo

A-star Algorithm Pathfinding Engine 1.4


  • Please log in to reply
56 replies to this topic

#1 Ansgar

Ansgar

    OM Studios

  • New Member
  • 333 posts

Posted 29 March 2007 - 10:07 AM

A-Star Algorithm Pathfinding Engine
version 1.4

This is a more advanced alternative to the Game Maker's built-in pathfinding engine.
It's perfectly suitable for grid based games with obstacles, or even mazes.

Compatible with GM 6 Registered and GM 7 Pro.



Change List:
1.4
- straight and diagonal costs are now saved in variables which can be changed with AStar_setAll
- the grid can have an offset
- you can now choose one of two coordinate systems and path returning systems
- most of the variables now have retrievable default values
- the estimate has been rewritten
- if the goal node is blocked, the engine doesn't even start searching
- more information in the scripts' headers
- corrected some lower/upper-case var errors
- enlarged the example grid - part is now maze-like, part map-like (with obstacles)
1.3
- you can set whether to allow diagonal movement and cutting through obstacles when moving diagonally (AStar_setAll)
- changed scripts: AStar_init, AStar_getNeighbors
- corrected a bug which caused the blocked direction setting to work only one-way
- enhanced the example - added a default maze and two new controls (see Example Controls in the game info)
1.2
- corrected the AStar_getCost script - previously, the system didn't return the shortest path in some cases
1.1
- fixed a bug which caused individual direction blocking not to work at all + some little polishments
- the scripts changed are AStar_init, AStar_setBlocked and AStar_setDirBlocked
1.0
- the initial release



Features:
  • 4- or 8- directional movement
  • cell blocking (obstacles)
  • individual direction blocking for each cell
  • allow/disable cutting through obstacles when moving diagonally
  • always finds the shortest path
  • fast and fairly easy to implement

More details are in the examples' game information (viewed in-game by pressing F1).
Sorry for the lack of proper documentation and script comments, I may improve it sometime later - but no promises.


Here are the download links:
GM6 Example (0.03 MB)
GM7 Example (0.04 MB)
GML File - just the scripts (0.01 MB)



Use this freely in your projects and modify it to your liking. Credit is appreciated, but won't be enforced through lawsuits :D.

This engine was created by Ansgar (Oskar Maxa) with some help from DFortun81.
It is based on David Brackeen's "Game Character Path Finding in Java" article, which can be found on the following address:
http://www.peachpit....p?p=101142&rl=1.



Please post your questions, bug reports, comments, ideas, ratings, suggestions, and all that stuff.

Edited by Ansgar, 02 June 2007 - 02:11 PM.

  • 1

#2 DFortun81

DFortun81

    The Fortunate One

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

Posted 29 March 2007 - 11:24 PM

This algorithm works well, I'm currently using it for my RPG Engine. Thank you for making it.

To those of you who don't want diagonals in your Paths:
1) Open AStar_getNeighbors.
2) Replace
for (c=0; c<8; c+=1) {
with this:
for (c=0; c<8; c+=2) {
3) There you go, no more diagonal paths. =]

Small Example for the AStar System: RPG Movement.

-DF81

Edited by DFortun81, 29 March 2007 - 11:47 PM.

  • 0

#3 coolsmile

coolsmile

    Programmer

  • New Member
  • 1346 posts

Posted 29 March 2007 - 11:50 PM

??? Wasn't one of these posted earlier :D
  • 0

#4 armymenis12

armymenis12

    "Tennis Addict"

  • New Member
  • 1040 posts

Posted 30 March 2007 - 04:31 AM

How do you make it so you can get the direction? So you can change image angle?
  • 0

#5 DFortun81

DFortun81

    The Fortunate One

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

Posted 30 March 2007 - 04:48 AM

How do you make it so you can get the direction? So you can change image angle?

<{POST_SNAPBACK}>

In the example I made, the direction is stored in the variable lastdir. Or you could simply use this:
image_angle = point_direction(xprevious,yprevious,x,y);

-DF81
  • 0

#6 Ansgar

Ansgar

    OM Studios

  • New Member
  • 333 posts

Posted 30 March 2007 - 04:35 PM

Here comes the first bugfix! The AStar_setDirBlocked script didn't work at all because of a stupid little thing I had forgotten - now it's fixed.
Please download version 1.1 from the first post.

And DFortun81, thanks for the example.

By the way, why do you think this topic has so few replies?
  • 0

#7 DFortun81

DFortun81

    The Fortunate One

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

Posted 31 March 2007 - 08:30 AM

And DFortun81, thanks for the example.

No problemo.

By the way, why do you think this topic has so few replies?

<{POST_SNAPBACK}>

I guess most people only require the built-in mp grid functions. Personally, this is better for me because it offers more features and can be drawn MUCH faster. (With MP grid, there is no way to access the cell's blocked/unblocked-ness.)

EDIT: Also, the built in are unmodifiable. For yours, I was able to make modified copies of the script and make it do more than just find a path. Pretty useful if you asked me.

-DF81

Edited by DFortun81, 31 March 2007 - 08:39 AM.

  • 0

#8 Jugado

Jugado

    GMC Member

  • New Member
  • 38 posts

Posted 03 April 2007 - 01:55 AM

This is very nice. Thanks for your effort. Just please give us a little more info how to use it.

Thanks again
  • 0

#9 Jugado

Jugado

    GMC Member

  • New Member
  • 38 posts

Posted 03 April 2007 - 07:12 AM

Ansgar and DF81,

The object following the path has to keep its proportions (height and width ) during the process? I was thinking to use a car and change its direction using something like this:


angle = point_direction(xprevious,yprevieous,x,y);
direction = angle;


Thanks for your answer.
  • 0

#10 Ansgar

Ansgar

    OM Studios

  • New Member
  • 333 posts

Posted 03 April 2007 - 01:45 PM

It makes no sense to change the direction variable, but you can definitely change image_angle.
If you put the code in the (end) step event along with an "if (path index == ...)" check, it will make the sprite face the direction in which the object is currently moving.
The engine just creates a path which you set to the object by calling path_start - just like with any other path - so you can change anything you want in the process of movement.

Hope it helps. :)
  • 0

#11 Jugado

Jugado

    GMC Member

  • New Member
  • 38 posts

Posted 03 April 2007 - 09:30 PM

Ansgar,

Thanks for the answer.

I made a mistake in the code, what I meant is:

angle = point_direction(xprevious,yprevieous,x,y);
image_angle = angle;

Thanks again

Edited by Jugado, 03 April 2007 - 10:12 PM.

  • 0

#12 Jugado

Jugado

    GMC Member

  • New Member
  • 38 posts

Posted 04 April 2007 - 08:14 AM

Ansgar,
Is it normal, fps goes from 30 to 2 when the path is being calculated? I am testing it using a map of 1920x1440, grid of 64x64 and most area is blocked
  • 0

#13 Ansgar

Ansgar

    OM Studios

  • New Member
  • 333 posts

Posted 04 April 2007 - 02:42 PM

Well, it's expected to freeze for a little while, it's made in GML after all. :skull:
However, if the speed bugs you too much, there's an AStar DLL made by homebrewpc in the DLL section - I guess it would be faster. It used to be quite buggy, but homebrewpc says he fixed all the problems (I can't confirm that though, I haven't tested it since then). Still, the disadvantage of it is the impossibility to customize the system.

And some GENERAL INFO:
If I have enough time, I'll probably try to make another version of the engine that supports hexagonal grid, and perhaps add some other enhancements. Stay tuned. :GM126:
  • 0

#14 Ansgar

Ansgar

    OM Studios

  • New Member
  • 333 posts

Posted 09 April 2007 - 05:10 PM

Version 1.2 is out!

The AStar_getCost script was buggy, causing the system not to find the shortest path in some cases. Now it's fixed, along with a little (probably unnoticable) speed gain.
Please redownload from the first post.

Oh and by the way, I changed the examples' filenames to AStar_gm6 and AStar_gm7.
  • 0

#15 Kyle_Solo

Kyle_Solo

    GMC Member

  • GMC Member
  • 1070 posts

Posted 11 April 2007 - 06:26 PM

Simply amazeing. (Get it? amazeing? nevermind...)
I'll be sure to find a use for this.

Edited by Kyle_Solo, 11 April 2007 - 06:27 PM.

  • 0

#16 Ansgar

Ansgar

    OM Studios

  • New Member
  • 333 posts

Posted 11 April 2007 - 08:11 PM

Glad you like it.

Simply amazeing. (Get it? amazeing? nevermind...) 

<{POST_SNAPBACK}>

:P
  • 0

#17 gamemakeriv

gamemakeriv

    GMC Member

  • Banned Users
  • 262 posts

Posted 11 April 2007 - 08:30 PM

Why does the blue block get its way through the intersection of the edges of 2 red blocks ?Fix that

NOt too accurate but nice :P .

#18 Ansgar

Ansgar

    OM Studios

  • New Member
  • 333 posts

Posted 12 April 2007 - 03:13 PM

You mean like this?
Posted Image
This isn't a bug, it's actually intended. It's true though that someone might not want it that way, so I'll make it optional.

EDIT:
Done. Version 1.3 has options to allow/disable diagonal movement in general and diagonal movement between obstacles, along with some other enhancements.
I hope you're happy now, gamemakeriv. :)

Edited by Ansgar, 12 April 2007 - 05:32 PM.

  • 0

#19 gamemakeriv

gamemakeriv

    GMC Member

  • Banned Users
  • 262 posts

Posted 12 April 2007 - 06:54 PM

Thanks buddy.That really helped.

#20 purple_pixie

purple_pixie

    GMC Member

  • New Member
  • 2647 posts

Posted 01 June 2007 - 11:40 AM

Brilliant work, Ansgar, cheers.

Now I can code my AI without having to do their path-finding too ... I tend to give up when I'm trying to do too many things at once :-D

Keep up the good work (even if it is now in "real" programming ;-) )

And btw, I'm a real programmer at work and trust me, GM is far more fun :-D

EDIT: I'm not sure if this is wanted, let alone needed, but I felt I had to:
I felt very limited by the hard-coded single path restriction of the engine, so with a few teeny changes I made a version that can use as many as you like:

http://www.obfuscate...r_multipath.gm6

Basically I just changed all the objPathFinder reference's into pathfinder (as a local variable) and when you create the path it saves the value of the created pathfinder object.
(And moved the obstruction create into a 1step alarm because otherwise their create gets called before the second player.

The one small drawback of my version is that all the scripts must be called from the "path owner" instance, as it is no longer "global"

If you want to use this don't even think about crediting me - give it to Ansgar: it's still his engine.

Edited by purple_pixie, 01 June 2007 - 07:05 PM.

  • 0

#21 Ansgar

Ansgar

    OM Studios

  • New Member
  • 333 posts

Posted 02 June 2007 - 02:04 PM

Thanks for the nice feedback. I'm glad I could help you.

Actually, I've already had a new version of this engine which allows you to choose between using one internal path or always returning the new one. I was just quite busy lately and forgot to upload it. :medieval:

So now get yourself ready for version 1.4!
Download links and the information on what's new are in the first post as usual.
  • 0

#22 Bathy

Bathy

    GMC Member

  • New Member
  • 504 posts

Posted 07 June 2007 - 03:05 AM

Looking good. My only suggestion is instead of creating a pathfinding instance during init(), adding an option to set the instance which holds the variables and we create it ourselves. This way we can have both local and global systems.

Edited by Bathy, 07 June 2007 - 03:07 AM.

  • 0

#23 Deri

Deri

    GMC Member

  • New Member
  • 70 posts

Posted 08 June 2007 - 10:57 PM

It works well. It always found a path when there was one. It lags a bit when calculating the path (about 2-3 seconds when going across the screen) but that probably can't be helped because of GM. One minor problem is that if I add a wall after it calculates the path then it will go through the wall! This is not good for a game where the player/other enemies are constantly moving, but should be fine in an RTS.
  • 0

#24 Ansgar

Ansgar

    OM Studios

  • New Member
  • 333 posts

Posted 10 June 2007 - 04:51 PM

Thanks for your comments.

My only suggestion is instead of creating a pathfinding instance during init(), adding an option to set the instance which holds the variables and we create it ourselves. This way we can have both local and global systems.

<{POST_SNAPBACK}>

OK... It'll be in the next version.

One minor problem is that if I add a wall after it calculates the path then it will go through the wall! This is not good for a game where the player/other enemies are constantly moving, but should be fine in an RTS.

<{POST_SNAPBACK}>

Yes, this engine is suitable for finding a stationary path, but it can't adjust it in real-time according to changes on the map.
  • 0

#25 Sammual

Sammual

    GMC Member

  • New Member
  • 32 posts

Posted 26 June 2007 - 04:56 PM

Any chance we can get a 6 directional movement ver? (Hex Tiles)

Features:

  • 4- or 8- directional movement


Thanks,
Dan
  • 0

#26 Ansgar

Ansgar

    OM Studios

  • New Member
  • 333 posts

Posted 27 June 2007 - 11:45 AM

I was thinking about adding hex grid support. However, there would be problems with indexing and possible different orientations of the grid... Useful suggestions are welcome here.

Still, I won't promise that I'll implement it at all, since my interests have moved a bit elsewhere during the last months.
  • 0

#27 Sammual

Sammual

    GMC Member

  • New Member
  • 32 posts

Posted 27 June 2007 - 03:43 PM

I was thinking about adding hex grid support. However, there would be problems with indexing and possible different orientations of the grid... Useful suggestions are welcome here.

Still, I won't promise that I'll implement it at all, since my interests have moved a bit elsewhere during the last months.

<{POST_SNAPBACK}>


There are only 2 different Hex grid orientations that I am aware of, one with vertical movement and diagonal horizontal movement and the other with horizontal movement and diagonal vertical movement.

The most common form of Hex grid indexing is using the same index system a simple square grid with every other row (or column) offset by 50% of the hex width (Or height).

Thanks,
Dan
  • 0

#28 IamCalle

IamCalle

    GMC Member

  • GMC Member
  • 444 posts

Posted 28 June 2007 - 03:10 AM

Well, the motion will be pretty static since you only have a 4/8 -directional movement. (I am thinking bots/A.I-controlled players for e.g. top-down games...)

Is there any possibility that you can let the user have a more free movement (maybe like sliding, sort of) ? (Do not worry about colission, I have a good code for that, might give it to others if they have problems with objects getting stuck :D ).

Edited by IamCalle, 28 June 2007 - 03:13 AM.

  • 0

#29 Ansgar

Ansgar

    OM Studios

  • New Member
  • 333 posts

Posted 28 June 2007 - 09:17 AM

There are only 2 different Hex grid orientations that I am aware of, one with vertical movement and diagonal horizontal movement and the other with horizontal movement and diagonal vertical movement.

The most common form of Hex grid indexing is using the same index system a simple square grid with every other row (or column)  offset by 50% of the hex width (Or height).

Thanks,
Dan

<{POST_SNAPBACK}>

Yeah, but there are some small dilemmas (like whether the odd or the even rows should be offset). I'll consider it.
Also I might add support for isometric grids.

Well, the motion will be pretty static since you only have a 4/8 -directional movement. (I am thinking bots/A.I-controlled players for e.g. top-down games...)

Is there any possibility that you can let the user have a more free movement (maybe like sliding, sort of) ? (Do not worry about colission, I have a good code for that, might give it to others if they have problems with objects getting stuck :D

I could probably do this by checking if there's anything between pairs of nodes in the returned path and smoothing the path accordingly.
To make the path smoother in another way (curved instead of angular), you can use the path_set_kind function.
  • 0

#30 IamCalle

IamCalle

    GMC Member

  • GMC Member
  • 444 posts

Posted 28 June 2007 - 12:24 PM

Will try that.
Hmm, I will go through the script again, and then just fool around a little bit. :D
  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users