GMLscripts.com

paul23

Member

Registered: 2007-10-17

Posts: 110

feedback:custom pathfinding

well this is something I've been working on for a long time already, more than a year currently.

I've tried to make a pathfinding algorithm. Which should be able to handle custom "movement cost" fields. I wanted to make a nice article for markup explaining how and why, however since I've currently a lack of decent time this won't be finished before christmas (if ever).

I managed to create a program around this subject already. It contains 3 "different" methods to find a path: Dijkstra's (I name it D* there), BFS (best first search) and Astar. I turned out to be pretty good (and I think I've commented it good enough to be released without a full guide). However I also discovered why people call gamemaker "slow": the scripts are actually so slow that it's almost impossible to use them in a real game!

The input:
most stats you can change in the top menu.. Like the the "cell size", type of algorythm and the pathfinding speed.
left mouseclick to place a new wall (with the size as a multiplier), right mouseclick to remove a wall.
control + leftmouse to place the "startpoint" and control+rightmouseclick to place the "endpoint" (pacman)

that's about all controlls there are currently. Please test my engine and leave some comment about it .
you can find it here

EDIT: some credits should also go to yourself for the highresolutiontimer (used to time the pathfinding speed) and lelo707 for the gwindows menubar (which is however far from perfect since it doesn't delete any data structures it used).

Last edited by paul23 (2007-10-21 15:52:38)

xot

Administrator

Registered: 2007-08-18

Posts: 1,239

Re: feedback:custom pathfinding

Hehe, I see you put "feedback" in your topic title, I guess as a request for feedback. I actually used it because the fire effect I posted uses a feedback algorithm.

This is a fantastic demo! I haven't played with it much yet, but I'm really impressed. Obviously, a lot of work has gone into this. I like that it graphically shows what's going on in its brain, setting iterations/frame to 1 really shows what's going on.

If script speed is a problem, you might consider using a scripting DLL like Lua. Keth is working on a Game Maker compatible version. I don't know how fast Lua is, but I'm hopeful it's a good deal faster than GML. I can think of a lot of applications for it, like this one. Still, encoding/decoding so much data as strings might be big speed issue as well.

http://gmc.yoyogames.com/index.php?show … &p=2378287

---

Abusing forum power since 1986.