New Pathfinding Example (extensionless)

Welcome to our brand new Clickteam Community Hub! We hope you will enjoy using the new features, which we will be further expanding in the coming months.

A few features including Passport are unavailable initially whilst we monitor stability of the new platform, we hope to bring these online very soon. Small issues will crop up following the import from our old system, including some message formatting, translation accuracy and other things.

Thank you for your patience whilst we've worked on this and we look forward to more exciting community developments soon!

Clickteam.
  • This is an example of a breadth first, flow-field pathfinding system.
    It doesn't require any extensions, and therefore should theoretically be compatible with any and all exporters.

    It is specifically designed to have a minimal impact on overall system performance, which it achieves by spreading the very computationally expensive pathfinding process across multiple frames (it does not update instantly). It is also adaptive, dynamically balancing pathfinding performance with system load, to ensure a stable framerate.

    Because of this, it is particularly well suited to games with:
    - very large maps.
    - a very large number of objects searching for the target(s).
    - multiple targets.

    For example, a Tower Defense clone, or a game with a horde of zombies chasing the player.

    It is NOT suitable for finding a path between just two points - for example, a point and click adventure game. It will work, but the A* algorithm would be much more efficient in this case.

    Note that this example uses a cellSize of 5 x 5 pixels only in order to demonstrate performance on a large map (100 x 100 tiles). This value can and should be adjusted before use in a game (it's in one of the Pathfinding object's alterable values).

    Please login to see this picture.

    Download:
    Please login to see this link.

  • This is insane. Very nice work

  • Thanks all!
    Not sure about that point and click pathfinding. I did get fairly close, and in theory it's not that tough - it was just all those awkward edge cases that kept causing problems!
    The code snippets here look interesting: Please login to see this link.
    The author specifically mentions "some extra code added for tolerance near the edges", so it might help with those edge cases... Not sure I feel like having another go at the moment though.

  • MuddyMole, here's something that has always been a challenge...
    Do you think a extensionless navigation mesh pathfinder is possible?

    Yes, I do. That's basically what we're talking about with "point and click pathfinding" (it's not quite the same as the method I was using, but it's very, very similar).
    Have a look at this page: Please login to see this link.

    Note where it says: "You will notice that this algorithm provides a wall-hugging path, since it use the vertices to generate the path. You can fix this by deleting useless points (if you can go from A directly to C without falling off the navmesh, then the point B is useless and you can delete it)."

    If I remember correctly (it was a couple of years ago now), that was where I was getting stuck. It would work fine in most cases, but floating point errors caused occasional but unacceptable bugs (I think it was if you started a new search with a starting point exactly on the edge of a polygon, but again I don't quite remember).

    This was the last version I made: Please login to see this link.

  • Looks great!
    Say, I was under the impression that the list object is one of the slowest objects in fusion Please login to see this link. so I'm intrigued by you using this in a performance oriented project and not just use arrays ?

  • Looks great!
    Say, I was under the impression that the list object is one of the slowest objects in fusion Please login to see this link. so I'm intrigued by you using this in a performance oriented project and not just use arrays ?


    Yes, sadly it is.
    LB's "Internal List" would be much better, but unfortunately it's for Windows only, so using it here would defeat the purpose, since you may as well just use a pathfinding extension.

    Unfortunately, array objects are just too different, and wouldn't work here. The main reason is that you can't delete a value, and have the other values shift to fill the gap. The A* algorithm also requires the values to be sorted, and there's no easy or efficient way to do that with an array.

    Personally, I think the most useful extension that doesn't exist, would be a kind of "List of Lists" (more like arrays in other programming languages).
    Ideally it would have an unlimited number of dimensions (referred to by value rather than X,Y,Z) - but failing that, certainly a minimum of 4 dimensions, because if you're storing map data, I find you always need X, Y, "Layer" (the same cell might contain terrain, monsters and items etc), "Properties" (again, you need to store the properties of each of those monsters or items).
    It would allow you to sort the values according to any of those dimensions. eg. "Sort by ascending dimension 0" or "Sort by descending dimension 2".
    It would allow you to delete values, and the others would automatically shift to fill the gap left.
    It would allow you to insert values, and the others would automatically shift to make space.
    It would need to work with all the exporters.

    If that extension existed, it would make things like pathfinding really quite easy and efficient.

  • Yes, sadly it is.

    We could probably add an "Internal" mode to the List object, so that you can use to choose either the current Windows control or an internal list. I'll check if this can be quickly done on all platforms (I know on some other platforms the object uses an internal list already if the control is hidden, I don't remember which ones).

  • Ah I see now.

    Since my current project depend on pathfinding I'm very interested in the subject.
    I've been using a solution based on [mention]SolarB[/mention] Please login to see this link. which I've modified to work with multiple targets. Basicly I'm using the Z dimension of the array to keep track of each calculated paths for each "actor" (each actor has an ID corresponding the Z value). It works great but I am worried about the number of fastloops that can potentially occur depending on map size etc. so having a solution that spreads across frames seems as the way to go but I'm unsure if I could implement in in my code or not. Maybe you have any thoughts or interest in this?

    (I'd post an example right now but it would take some time to remove my game assets but if you're interested I'll try to do it when I have time)

  • We could probably add an "Internal" mode to the List object, so that you can use to choose either the current Windows control or an internal list. I'll check if this can be quickly done on all platforms (I know on some other platforms the object uses an internal list already if the control is hidden, I don't remember which ones).

    If it turns out to be an easy fix, then there's no reason not to :)
    It's not so important for this particular project though, as anyone making a Windows game can just just a pathfinding extension.


    It works great but I am worried about the number of fastloops that can potentially occur depending on map size etc. so having a solution that spreads across frames seems as the way to go but I'm unsure if I could implement in in my code or not.

    Honestly, I'm not sure it would be so easy to retrofit to an existing system. I'd test it first, to see if performance actually is a problem - if you have a fairly small map it might be fine anyway.

    The biggest problem I can think of is that when the pathfinding process is spread over multiple frames, the objects still need to be able to navigate while it's going on.
    My example gradually overwrites the path array. The previous version used two separate arrays - the pathfinder would write values to one array, while the objects would read values from the other, and then they'd swap. Either system would be a fair amount of work to retrofit.

    The other alternative would be to make it so that as soon as the pathfinding process finishes, each object would immediately trace a path from its current location to the target, and store the entire path in an alterable string as a sequence of directions, so that it no longer needs to read data from the path array. You'd also want to trace a path from the start point to the target, to be used by any objects that get created while the pathfinding process is going on. That's not so efficient though...

  • Surprisingly messing with this I confused it and to many objects maxed out the mfa. This caused the outside of the entire example to be filled with the blue objects that move. FPS dropped to 30 and then it just gave up. The mfa did not crash but the objects stopped trying to reach the end.

    I drew a spiral circle from the center to roughly 25% from the borders.

Participate now!

Don’t have an account yet? Register yourself now and be a part of our community!