Jump to content


Photo

Astardll - Quick A* Algorithm Pathfinding


  • Please log in to reply
207 replies to this topic

#1 homebrewpc

homebrewpc

    GMC Member

  • New Member
  • 651 posts

Posted 28 March 2007 - 01:34 AM

AStarDLL (V3)
Works in GM6 and GM7.

New Version, check the features below.

AStarDLL is a quick and easy to use pathfinding DLL that uses the A* Algorithm. It has the following features:

-Can place obstacles
-Can block off cells from certain directions (8-dir blocking)
-Can set the "costs" for moving diagonally and non-diagonally
-Can set "cost" for moving into a specific cell
-Can set "cost" for moving into a specific cell from a specific direction
-Can set whether to allow diagonal movement or not
-Can set whether to allow cutting edges of obstacles when moving diagonally or not
-Has a function that centers the object in the cells when following a path
*NEW*-Has functions to return whether a cell is an obstacle, whether a cell is blocked from a certain direction, the individual cost of a cell, and the individual cost of a cell from a certain direction.
-Request your ideas!

This DLL can get anywhere in this maze as well as anything you create:
Posted Image

The download comes with a GM6 Example (Works in GM7), AStarDLL.dll, ReadMe, and the Scripts needed. To understand the scripts and how to use them check out the ReadMe.

IF YOU ENCOUNTER A PROBLEM, TAKE A SCREENSHOT

Download AStarDLL (Reply Please :blink: )


If you encounter any errors that say "Variable astarR_anything does not exist." even though you have initialized the DLL, it is because the initialization is happening after you call those events. To prevent this, do not call anything related to the DLL in the creation events of other objects, make them on an Alarm set to 1.

If you download or use source please reply asking permission.

DELPHI SOURCE CODE: CLICK ME

Thank you for downloading!
HomebrewPC

Edited by homebrewpc, 25 September 2007 - 11:39 PM.

  • 0

#2 DFortun81

DFortun81

    The Fortunate One

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

Posted 28 March 2007 - 01:47 AM

In the creation code of the obstacle, you need to add this piece of code after aligning it to the grid:
astar_setobstacle(x,y);

Oh, and this needs to go in the Left click event:
astar_setfree(x,y);
instance_destroy();

Thank you so much for making this, hopefully, it will speed up detection a lot.
-DF81

Edited by DFortun81, 28 March 2007 - 01:54 AM.

  • 0

#3 homebrewpc

homebrewpc

    GMC Member

  • New Member
  • 651 posts

Posted 28 March 2007 - 01:57 AM

Yeah, thanks for mentioning that obstacle thing, just realized that when I checked. Re upload in a minute.

Thanks and Your Welcome,
HomebrewPC

EDIT: Re-uploaded, but I have to go now, will check tomorrow.

Edited by homebrewpc, 28 March 2007 - 01:59 AM.

  • 0

#4 Ansgar

Ansgar

    OM Studios

  • New Member
  • 333 posts

Posted 28 March 2007 - 04:54 PM

Thanks for making this, I was also waiting for this, as I said in DFortun81's topic.
Great job.

However, when I played the example, I noticed that it freezes every time the engine takes a wrong way searching and has to return one step back (in other words: when a node is returned from the closed list to the open list). This is an example screenshot of the frozen game; the yellow cross marks the cell I clicked at.
Posted Image

By the way, I'm working on my own attempt on implementing A* Algorithm into GM, using plain GML (despite what I wrote in DF81's topic). I'll post it if it works out well.
I may be naive, but so far it doesn't seem too slow. DFortun81, did you use objects in the engine? (I use maps.)

EDIT: Holy cow, I'm almost done and it doesn't lag at all!
At the moment I've got it working in a totally unpolished user-unfriendly version, but I can still upload it if you'd like to see it. :blink:

Edited by Ansgar, 28 March 2007 - 06:37 PM.

  • 0

#5 DFortun81

DFortun81

    The Fortunate One

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

Posted 28 March 2007 - 08:02 PM

I use data structures, the only objects in the level are a controller object and the player.

I am also receiving the same error as Ansgar. It will randomly freeze when there is a path to the location that I could see, but the DLL could not.

Another small bug: When computing a path, it ignores diagonals when there are obstacles on the two cells next to the diagonal for the most part. Rather than taking the diagonal path, it goes all the way around the wall to get to the destination.
Here is an image showing this:
Posted Image
The X indicates the starting location and the circle represents the end location.

-DF81

Edited by DFortun81, 28 March 2007 - 08:03 PM.

  • 0

#6 homebrewpc

homebrewpc

    GMC Member

  • New Member
  • 651 posts

Posted 28 March 2007 - 08:10 PM

Ansgar: I am working on that, I think it will be a simple fix. I can't do it at the moment though.

DF81: Its supposed to go all the way around. If it goes straight through the blue ball will intersect with the obstacles. I did that on purpose. I'll make this an option in the grid set script if you want.

Thanks for the comments!
HomebrewPC

Edited by homebrewpc, 28 March 2007 - 08:31 PM.

  • 0

#7 Ansgar

Ansgar

    OM Studios

  • New Member
  • 333 posts

Posted 28 March 2007 - 08:38 PM

OK, here is what I've put together so far: My A-Star
It's based on a Java algorithm I found somewhere on the net. It was too generic, so I first made a particular pathfinding implementation of it in Java (just for my learning purposes - I'm a Java novice) and then converted it for Game Maker. It has just 4 directions at the moment, but it's a matter of minute(s) to add the other four (by modifying the AStar_getEstimatedCost and AStar_getNeighbors scripts).

Enjoy. :)

EDIT: I updated the engine (or example or whatever you want to call it), and I'll soon probably make a new topic for it.

EDIT 2: Done. Link in my signature. :D

Edited by Ansgar, 29 March 2007 - 10:13 AM.

  • 0

#8 DFortun81

DFortun81

    The Fortunate One

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

Posted 28 March 2007 - 09:30 PM

That's a pretty cool, but the DLL supports directional checking for each cell rather than just blocked/unblocked. Good job though.

-DF81
  • 0

#9 homebrewpc

homebrewpc

    GMC Member

  • New Member
  • 651 posts

Posted 29 March 2007 - 12:27 AM

And if you have massive grids with tiny cells, that is probably going to slow down.

HomebrewPC
  • 0

#10 9_6

9_6

    Guest

  • GMC Member
  • 3627 posts

Posted 29 March 2007 - 04:47 AM

Yet it's still better than something that keeps freezing the program because it actually works in most cases (it sometimes slips through solid blocks though).
  • 0

#11 homebrewpc

homebrewpc

    GMC Member

  • New Member
  • 651 posts

Posted 29 March 2007 - 04:09 PM

Yet it's still better than something that keeps freezing the program because it actually works in most cases (it sometimes slips through solid blocks though).

<{POST_SNAPBACK}>


I know how to fix it, I haven't had the time. I will update it tonight or tomorrow.

Thanks,
HomebrewPC
  • 0

#12 coolsmile

coolsmile

    Programmer

  • New Member
  • 1346 posts

Posted 29 March 2007 - 04:22 PM

Yeah, it did that to me also :D
I remember the first version...
  • 0

#13 homebrewpc

homebrewpc

    GMC Member

  • New Member
  • 651 posts

Posted 29 March 2007 - 04:33 PM

This is the first version...what are you talking about?

HomebrewPC
  • 0

#14 Daniel-Dane

Daniel-Dane

    GMC Member

  • New Member
  • 3581 posts

Posted 29 March 2007 - 04:38 PM

The script version DF81 made :D.
  • 0

#15 Ansgar

Ansgar

    OM Studios

  • New Member
  • 333 posts

Posted 29 March 2007 - 05:40 PM

Huh, someone is definitely mixing up something here, but I'm not sure who and what... :D

By the way, homebrewpc, do you mind I used the same example layout as you in my AStar engine? If you do, I'll change it, I was just lazy. ;)
  • 0

#16 DFortun81

DFortun81

    The Fortunate One

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

Posted 29 March 2007 - 06:55 PM

The script version DF81 made ;).

<{POST_SNAPBACK}>

Yeah, it was a really slow script in my DIA RPG Engine.

Huh, someone is definitely mixing up something here, but I'm not sure who and what... :D

<{POST_SNAPBACK}>

Well not really, I made a topic a while back asking for a DLL that did A* calculations with 8 directional checking because I was tired of my path finding algorithm going extremely slow. I haven't updated the engine to include either of the new methods yet, so you can still view its horribleness if you download it.

But yeah, when you clear up the freezing bug, let me know.
-DF81
  • 0

#17 homebrewpc

homebrewpc

    GMC Member

  • New Member
  • 651 posts

Posted 29 March 2007 - 08:11 PM

Huh, someone is definitely mixing up something here, but I'm not sure who and what... :D

By the way, homebrewpc, do you mind I used the same example layout as you in my AStar engine? If you do, I'll change it, I was just lazy. ;)

<{POST_SNAPBACK}>


Let's put it this way, if my topic turns into people talking about your script, I'm going to be mad.

I'm going to work on that freeze error now, probably won't take that long.

HomebrewPC

EDIT: Fixed all known problems, in the process of uploading.

Edited by homebrewpc, 29 March 2007 - 09:13 PM.

  • 0

#18 novaz

novaz

    GMC Member

  • GMC Member
  • 587 posts
  • Version:Unknown

Posted 29 March 2007 - 09:27 PM

hi, when you click with left button there's an error for global left
pressed. But the programs works :D

Edited by novaz, 29 March 2007 - 09:28 PM.

  • 0

#19 homebrewpc

homebrewpc

    GMC Member

  • New Member
  • 651 posts

Posted 29 March 2007 - 09:30 PM

Crap...that's not an error. That is what the DLL returned, I was just showing it as an error so the text would not get cut off. I was using that to find where the freeze bug was happening. Ill fix that.

HomebrewPC

EDIT: Re-uploaded

Edited by homebrewpc, 29 March 2007 - 09:32 PM.

  • 0

#20 novaz

novaz

    GMC Member

  • GMC Member
  • 587 posts
  • Version:Unknown

Posted 29 March 2007 - 09:43 PM

thanks for the work. Unfortunately the program still freezes after some
pathfinding, if you create a little maze. Maybe there's some bug in
the example, not in the dll.
  • 0

#21 homebrewpc

homebrewpc

    GMC Member

  • New Member
  • 651 posts

Posted 29 March 2007 - 09:45 PM

There is no way AStar can get though a maze, but does it freeze other than when in a maze? And if so when?

I think Im going to add some freeze security and so after width*height*2 loops go by that it stops and returns an empty string.

Thanks,
HomebrewPC

Edited by homebrewpc, 29 March 2007 - 09:45 PM.

  • 0

#22 novaz

novaz

    GMC Member

  • GMC Member
  • 587 posts
  • Version:Unknown

Posted 29 March 2007 - 09:47 PM

i mean a "little" maze, not a big one. But it freezes also when there
are few obstacles, i dont know why.
  • 0

#23 homebrewpc

homebrewpc

    GMC Member

  • New Member
  • 651 posts

Posted 29 March 2007 - 09:53 PM

It doesn't freeze for me if I have little obstacles, a little maze, or a ton of obstacles. Uploaded a new version with that freeze protection idea though.

HomebrewPC

EDIT: Take a screenshot of one time it freezes please Novaz.

Edited by homebrewpc, 29 March 2007 - 09:54 PM.

  • 0

#24 novaz

novaz

    GMC Member

  • GMC Member
  • 587 posts
  • Version:Unknown

Posted 29 March 2007 - 09:55 PM

in this picture, it freezes everytime you click on a wall. I tried 3 times.
Posted Image
  • 0

#25 homebrewpc

homebrewpc

    GMC Member

  • New Member
  • 651 posts

Posted 29 March 2007 - 09:56 PM

...Hmm, the DLL wouldn't do that. It checks if the End point is an obstacle and then stops. I don't know if that is the program then or not.

HomebrewPC
  • 0

#26 DFortun81

DFortun81

    The Fortunate One

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

Posted 29 March 2007 - 11:12 PM

It still freezes for me, too. I'm going to try something... I'll reply a little later with my result.

EDIT1:
Alright, I've isolated the error. It involves your internal obstacle system...

EDIT2:
Okay, I changed 2 of your scripts to function ONLY with the 8 Direction rather than obstacles.

Replace your script, astar_setobstacle, with this code:
//astar_setobstacle(x,y)
var ar0,ar1,i;
ar0=floor(argument0/global.astarR_cellwidth)
ar1=floor(argument1/global.astarR_cellheight)
//external_call(global.astarR_setobstacle,ar0,ar1)
for(i = 0;i < 8;i += 1;)external_call(global.astarR_setdirblocked,ar0,ar1,i,1);

Replace your script, astar_setfree, with this code:
//astar_setfree(x,y)
var ar0,ar1,i;
ar0=floor(argument0/global.astarR_cellwidth)
ar1=floor(argument1/global.astarR_cellheight)
//external_call(global.astarR_setfree,ar0,ar1)
for(i = 0;i < 8;i += 1;)external_call(global.astarR_setdirblocked,ar0,ar1,i,0);

It will no longer freeze. :]

-DF81

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

  • 0

#27 homebrewpc

homebrewpc

    GMC Member

  • New Member
  • 651 posts

Posted 30 March 2007 - 12:23 AM

Thanks a ton, I think I know exactly where the error is. I will edit/reply/update when I fix it.

Does it work for your purpose now then?

Thanks,
HomebrewPC

EDIT: Can you take a screeny of what the grid looks like when there is an error please?

EDIT2: Ohhhhh...I get it...your just setting all eight positions as non-enterable...that would be smart. Screw fixing the error, Ill just change those and upload it.

Edited by homebrewpc, 30 March 2007 - 12:53 AM.

  • 0

#28 DFortun81

DFortun81

    The Fortunate One

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

Posted 30 March 2007 - 12:55 AM

Thanks a ton, I think I know exactly where the error is. I will edit/reply/update when I fix it.

No Problem.

Does it work for your purpose now then?

<{POST_SNAPBACK}>

It does, but it doesn't find the fastest path to a particular location.

In some cases, it wont even get past easy to find cells...
Posted Image
-Red Squares are the obstacles.
-Blue circle is the player.
-Yellow Squares are the cells that I have clicked.
Of all of the yellow squares, only the top 2 work. (Where the player is and the cell above it.)

I don't understand how the 3rd cell didn't work, but you get the picture.
-DF81
  • 0

#29 hughman

hughman

    GMC Member

  • GMC Member
  • 568 posts

Posted 30 March 2007 - 12:59 AM

sounds great... doesn't seem to be true A* in that I would think A* would go across a diagonal instead of only cutting off one corner and other than that going left/right/up/down
  • 0

#30 homebrewpc

homebrewpc

    GMC Member

  • New Member
  • 651 posts

Posted 30 March 2007 - 01:34 AM

Ok, I made it so it goes more diagonal for you hughman. It will go diagonal at the same value as left, right, up, and down now.

Also, as for our obstacle problem, try the one I uploaded and tell me if it works for you...works for me...

It still cannot get through your grid though, but sometimes it does depending on where the blue dot is.

As far as making a normal non-maze game though, I think this would work.

Thanks,
HomebrewPC
  • 0




1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users