Pixel Movement

by Forum_account
Pixel Movement
A pixel movement library for isometric and top-down maps.

Dense Object support for A*

ID:472409
 
Mar 8 2012, 10:45 pm
Keywords: astar, object
Applies to:A*
Status: Open
Issue hasn't been assigned a status value.
I added some impromptu dense object support for the A* algorithm, as it doesn't (currently) support this natively. :)

obj
    /*
        astar_density is used in the A* algorithm
        to determine if the object should be considered
        dense or not.

        By default, all dense objects will be considered
        dense for A*, but can be over-ridden by setting
        astar_density to 0.

        Likewise, non-dense objects can be considered
        dense in A* by setting astar_density to 1, while
        they're still technically non-dense for all other
        intents and purposes.
    */
    var astar_density = null


    New()
        ..()
        if(astar_density == null)
            astar_density = density

Path
    add(turf/t)
        for(var/obj/o in t)
            if(o.astar_density)
                return
        ..()


Would it be possible to have this included in a release of the library, in whatever better way you will undoubtedly come up with?
Mar 10 2012, 9:25 am
Making the add() proc separate from the rest of the algorithm wasn't an accident ;-)

Previously mobs could walk through each other by default so this wasn't an issue. You could use can_bump() but then you get into other issues. If path planning is tile-based, pixel-based obstacles complicate that. I think having a separate variable to determine if the object blocks the entire tile is fine. I don't know if I'll call it astar_density, but this approach looks good.
Mar 10 2012, 9:28 am
Oh, it might be better to call ..() first in add(), that way it'll check for more obvious conditions that'd cause add to fail (the tile was already checked, the turf is dense or null, etc.):

Path
    add(turf/t)
        if(..())
            for(var/obj/o in t)
                if(o.astar_density) return 0

        return 1
Mar 11 2012, 8:35 pm
Yeah, I have ran into some problems with pixel based density, since this just checks for tiles and I'm not familiar enough with the library yet to get into things like that.

I do really like how your libraries are designed and that they're easy enough to use and navigate that I can pick them up and work with them (I've only been using this and some others for a few weeks now). Keep up the good work.
Mar 12 2012, 3:40 am
The problem with pathfinding is that things get very game-specific very fast. If your game has spike pits that you'd want the pathfinding to avoid, there's no way for the library to know that. If your game has teleporters, there's no way for the library to know how they work and use them to plan paths. Even simple obstacles can cause problems because there's no way for the library to know if the mob can jump over the obstacle, push it out of the way, etc. As nice as it'd be, there's just no way it'll be sufficient. I was just hoping to create something that's more flexible and more useful than DM's walk_to() proc =)

You can completely change how path finding/following works by overriding the move_to() and follow_path() procs. follow_path() is called from the mob's action() proc. move_to() creates a path and the default behavior of the action() proc is to call follow_path (if the mob has a path to follow). Assuming you have pixel-based path planning it wouldn't be hard to make the library use it, it's just the pixel-based path planning that's the problem.

I do really like how your libraries are designed and that they're easy enough to use and navigate that I can pick them up and work with them (I've only been using this and some others for a few weeks now). Keep up the good work.

Thanks! If you have any comments or suggestions, don't hesitate to post them. The libraries are easy to use because of all the user feedback I've taken into account.