Pathfinding without the PO object? Ideas?

[AnotherFreak]

Is there a way tomake custom pathfinding, without the PathfindingObject? It is buggy. I was thinking about using loops, detectors and checking the distance between point A and point B, but can't really find an interesting idea how to get all of this to work. Have any of you constructed something like this? Could you spare an example, or at least give a few ideas?

[AnotherFreak]

I hope that i posted this in a good forum.

[Sphax]

Pathfinding is a really big problem.

What's the problem you have with the object ? It works very well in the last version...

[Brandon]

Well, I guess for a type of pathfinding you can use x,y greater than less than events.
Like:

+X("Active")< Xmouse
Set X of active to X("Active")+1

[Sphax]

That's not a pathfinding... A pathfinding is really really complicated and several algorithms exist... Usually, it's the A* which is used in the games (it's the algorithm which is used in the PF object I think) but the better algorithm is djikstra which is slow (but with modern computers, more and more games use it with some optimizations).

See this good wikipedia article : http://en.wikipedia.org/wiki/Pathfinding

[DavidN]

Is Djikstra really that much better? I thought that A* always gave the optimal route.

I'd imagine that A* would be just about possible to do in MMF itself through fastloops, but it's definitely the kind of thing that I'd prefer to hand over to an extension.

[Random]

Depending on what you need the pathfinding for, the are various solutions. Although I don't think any of them is really better than using the pathfinding extension.

* use detectors to avoid small obstacles (e.g. check if there's a route around them, to the left or right)
* use node objects that are places throughout the map that check in the beginning if they have sight contact and store the IDs of nodes they can see. Then if your objects needs a path you can run through the nodes to find one that leads to your target
* use nodes that contain information, which directions are possible at their position and when your object reaches that node, use the direction that will most likely go to the target
* if it's for enemies that are just supposed to track the player for a bit, use "last seen"-coordinates that stem from line-of-sight with the player (if player is not visible, go to where you've last seen him and there go the direction you've last seen him going).. this is quite reliable and makes for cool and realistic enemies

[Dynasoft]

Is Djikstra really that much better? I thought that A* always gave the optimal route.

Djikstra is always guaranteed to be the optimal route, A* is guaranteed optimal as long as the heuristic is good.

I'd imagine that A* would be just about possible to do in MMF itself through fastloops, but it's definitely the kind of thing that I'd prefer to hand over to an extension.

Somewhere in the old forum I think I posted an example of pathfinding without the pathfinding object, but the events definitely weren't pretty and it was pretty slow.

EDIT: Found it! http://www.clickteam.com/CTforum/showthreaded.php3?Cat=&Board=upload&Number=179097& Search=true&Forum=upload&Words=Dynasoft&Match=User name&Searchpage=3&Limit=25&Old=allposts&Main=17909 7

EDIT2: I can't remember if that file is Djikstra or A* pathfinding. I know I did one for Jamagic that was definitely Djikstra, and I've definitely written an A* pathfinder in c++, but I can't remember what that MMF one is and I can't open it here

[Sphax]

Djisktra is a lot better in results than A* but Djisktra, if coded whithout algo optimization, is pretty slowest than A*.

Djikstra is the algorythm used for routes finding in roads networks (PnD or websites like Mappy.com).

[UltimateWalrus]

http://www.policyalmanac.org/games/aStarTutorial.htm

This is a good tutorial on the A* algorithm --- much more easy to understand than the wikipedia article. I think that you could implement this in MMF but you would need to find a good way of implementing an "open list" and a "closed list" (maybe arrays)? From there, it'd just be a matter of using fastloops. I don't think it would drag down performance too much if you used it carefully.

From what I've read, A* gives identical results (shortest path) as the Djikstra algorithm when the heuristic is good and you know the exact point you're searching for. In the above example, I would change the heuristic to measure the distance when moving diagonally is allowed (this should give a perfect heuristic).