@winkclub23 it's called travel pillow and it only exists in my mind for now sry ;_; (Today)

@r_rdein so far I'd say it leans a little bit more toward fighting enemies than platform challenges? but I dont have a lot of items yet (Today)

@konjak could u (Today)

@konjak do what you feel. the platforming is really snappy and felt weird to me at first, but once I got used to it it made sense ~I M H O~ (Today)

I've been playin' Hollow Knight and I like it A LOT, feels super fun, dark & spooky & somehow cute at the same time~ t.co/kZTPFlbBB5 (Today)

@theBanov keep a cycle of 12 hour sudafed running. I'm not even sick and I'm going to be doing that for GDC. sleep as much as you can. (Today)

RT @TeamCherryGames: The wait is over! Grab @HollowKnight and start exploring the strange, amazing, insect world of Hallownest! #Steam: htt… (Today)

@flurrycow get plenty of sleep and eat well (Yesterday)

@pietepiet jfc paul (2 days ago)

@midio here take this HM01 (2 days ago)

@konjak sounds good <3 <3 (2 days ago)

RT @MattThorson: Celeste is coming to Nintendo Switch in 2017! See you on the mountain :) t.co/TMOon1iCAs t.co/Aqm2AXcqKo (2 days ago)

it always amazes me when making games you can jam out a playable thing in a weekend but then it still takes somehow 3 years to complete (2 days ago)

RT @NightInTheWoods: NIGHT IN THE WOODS: AVAILABLE ON STEAM AND BASICALLY EVERYWHERE ELSE t.co/oPPY4OY754 (3 days ago)

RT @NightInTheWoods: (Night In The Woods will be out in all its glory on PC/Mac/Linux at 1pm EST tomorrow. get hype. etc.) (4 days ago)

@ADAMATOMIC @nealen y yes I'll have this burger... *wipes tears* With two patties (6 days ago)

@ADAMATOMIC @nealen help t.co/Yz9wHJq2St (6 days ago)

RT @ishisoft: The beach is Leilani's territory! New Leilani's Island devlog update t.co/t7Pj7xSzeh 🌺🌴🍍 t.co/OyhOEsDGbM (6 days ago)

looking forward to hanging out with fellow introvert devs at gdc. lets all sit in the same room together with laptops in comfortable silence (7 days ago)

@ChrisBellDesign oh whoops I also read that as expo pass. I think that's supposed to be ONLY expo hall, but you can be sneaky sometimes. (7 days ago)

follow
search

2014 - 4 - 9 / 4:11 am / general

Dev Log: Pathfinding Fun

Image

Like a cat chasing a laser pointer, I have some basic enemies chasing paths through the skies.

Right now I'm using A* and although I don't really know what is going on that much, I have a system that enemies can use to find paths to their destinations. Normally I wouldn't bother with any sort of path finding, but for this game I want enemies to have to intelligently navigate through obstacles that the player is deploying, so my usual "make up a path finding function that doesn't actually path find but sometimes works out" function wont cut it.

What I have currently is a pretty straight forward set up:
- One PathFinder instance in my Scene. It extends Entity so that it can be updated by the scene automatically.
- Enemies request a path from PathFinder and also register a callback Action with the request.
- The PathFinder instance adds the request to the queue.
- Every update the PathFinder will take the top item of the queue and start the path finding process.
- The actual A* algorithm and calculations are run on a BackgroundThread so that the game can continue while this is going on.
- When the path is done calculating the callback is fired, and the enemy now knows about its path.
- It chases down the nodes that were added to its path.

I made a quick change to the A* algorithm as well under the sage advice of Chevy Ray: I'm using a maximum movement value that will stop the algorithm if the move costs become too high. The result is that the algorithm will return a partial path to the final target instead of the entire path (which could take a long time to calculate in a set of nodes with a lot of open spaces.) So with this in mind the rest of my logic looks like this:

- When the enemy reaches the last node, it checks to see if its close to its intended target.
- If not it requests a new path to its target.
- If it is then it will enter its attack behavior, whatever that is.

So far this seems to be working out pretty well. I have a lot of work to do with how enemies will end up treating their path nodes in regards to their actual movement. Right now they just try to move toward each node, but with a lot of nodes together they end up having some trouble, like that wiggling in the animation above. Something like an averaged out path between a lot of nodes might work better... hmm!

4 Comments
Avatar

2014 - 4 - 11 1:08 PM

Daniel

This is confusing hahaha

Avatar

2014 - 4 - 11 2:05 PM

Kyle

You're telling me ;D

Avatar

2014 - 4 - 12 2:23 AM

Oliver

Looking sweet! :-) Hmm, if the nodes are this close together, maybe some kind of weighted velocity vector made of the next x nodes, weighted by their current distance to the fishie could smooth out the animation a bit*scratches head*

Can't wait to see what kind of game this is going to be! :D

Avatar

2014 - 4 - 15 9:23 AM

Anonymous

Often times actor's turn towards their desired heading before moving via a rotation lerp or a custom animation based on the size of the angle. Having the pathfinder return a starting direction vector as soon as possible even if the path is not nearly complete will allow the actor to look smarter by starting to turn towards the desired heading while pathfinding is still in progress. This helps hide the pathfinding latency and makes your actor more responsive.

Avatar

Post your comment!

POST COMMENT

about

About

Hi! My name's Kyle, and I make video games most of the time in Denver, Colorado. Here you will find my thoughts, games, websites, doodles, and other stuff like that. I worked on Snapshot, Offspring Fling, and a whole bunch of other games. I also created and maintain Otter, a 2d game making framework. If you want to get a hold of me use the form on the bottom of the page, leave a comment, or just tweet at me. I try to post three times a week. Thanks for stoppin' by! You're the coolest.

blog stuff

categories

tags

archives

facebook

videos

Do you want to make a Let's Play of one of my games, or a just a video featuring footage of my games? You have my full permission to do so! Even if you are monetizing your videos, you still have my full permission to use any footage from any of my games. Go for it!

contact

Your message has been sent! Thanks :)
SEND MESSAGE