laarcnew | comments | discord | tags | ask | show | place | submitlogin
Pathfinding for Tower Defense (redblobgames.com)
3 points by sillysaurus to dev gamedev 695 days ago | 4 comments


4 points by JungleCat 695 days ago

> For Tower Defense style games, I’ve used it to find paths from all locations to a given location, instead of using A* repeatedly to separately find a path for enemy.

I usually loose interest in my prototypes loooong before they turn into fully fledged games, but the concept of flow fields, or scents as I called them, I had a lot of fun with.

I did it on the GPU: each enemy sets a channel of the pixel of the "scent map" that corresponds to the tile they're on to full value every X milliseconds, and a shader diffuses the scent (at much higher frequency), also reading from a heightmap texture (so in addition to walls it can take max climb height and the max distance to safely drop from into account). Each scent type has a relative rate at which it decays (e.g. "multiply with 0.99 each pass"), as well as a (very small) absolute amount that gets subtracted (so scents can have an effective max range at which they reach 0, instead of always diffusing all over and never quite reaching zero).

Of course just enemies putting out their own scent isn't that useful, other than to spread around the map. So when an enemy spots the player, the player puts out player scent (this is totally separate from the enemy scent) for the faction that enemy is part of, as long as the player is seen. There's also another scent for sounds the player makes. These scents spreads quickly, so nearby enemies hone in the player (or to sound though that's much less attractive to them), but for that they don't just use the player/sound scent, they also substract the scent of their faction mates from it.

The glorious end result was that if the values are tweaked just right, the enemies closest to the player will always take the direct route to where the player scent is strongest, but enemies farther behind might prefer a route that is a tiny bit longer, but has less enemy scent on it (it was very noticeable in maze like tilemaps, not so much in open maps). They "naturally" flank and surround the player, if you will. If the player is no longer where they were last seen, they'll bump around for a bit and disperse ^^

Reading from the scent textures to make decisions all the time for many enemies can get costly, but I also did all of this rather naively, I'm sure there's a way to make it a lot faster. I just evaluated the 3x3 tiles around each enemy for decisions, and with some inertia that actually looked just fine, but with 5x5 or more one could pick the best tile in LOS, that would probably be better.

-----


This is way cool. Is the source code up somewhere? Even if it doesn't run, it would be neat to dig through it.

-----

3 points by JungleCat 695 days ago

Well it does run, but the "code" is, well... just me playing around with a lot of things when I feel like coding but not like being productive, the whole "game engine" thing was always more to experiment than anything "real", and the opposite of something I'd be proud to show off.

So, here you go:

http://jsboxx.sandboxx.org/?revret

For some reason the textures don't don't load in FF (works fine on localhost oh well), and it's much faster in Chrome anyway, so use Chrome. You need a good GPU for what it does because my code sucks bad ^^

This isn't in the state it was in, since I kept playing around with it, the map is just generated flat (that is, either walls or ground) atm, I'm pretty sure I had toggleable shadows in there and some other things, I probably commented and broke things -- but the scents work. Just glancing at the code I'm not up for digging into it at this moment, eurgh. I write so much better code now that I cannot even read this! Feel to try, but I'm not sure it will be more helpful than the description of the rough idea I gave. Viewer discretion advised, no liability, if you tell anyone I wrote this I'll deny it, etc. :D

God knows what the "controls" are... here are some:

    T     teleport
    M     move camera where mouse is (if the viewport was the whole map, that is)
    Q/W   zoom in/out
    WASD  move
    LMB   fire
    Keypad 2:     toggle displayed "scent channels" for player
    Keypad 3,4+6  do same for other factions (no clue what's up with 5, the scent drawing confuses me loads, FWIW press F1 to toggle showing the faction/channel #)
    3 and B       toggle line of sight to enemies/allies, and draw them thicker? man, I have no clue what any of this is supposed to be...
    TAB    crash the game
you can also use CTRL + mousewheel to change the resolution, that is the one thing I always liked a lot about this "engine" hehe.

-----


This is awesome! http://jsboxx.sandboxx.org has a bunch of interesting work too. I've been working on a "Show laarc" system; let me know if you'd like to showcase this.

Seeing cool hacks like this has been one of the best parts of laarc.

-----




Welcome | Guidelines | Bookmarklet | Feature Requests | Source | Contact | Twitter | Lists

RSS (stories) | RSS (comments)

Search: