Steering pathfinding demo

General Discussions
#1

Hey guys,

I thought you all might be interested in this. I’ve been working on a Diablo/roguelike for a while and I decided I really hated the grid-based moving my characters were doing (smooth movement within a grid). It looks sterile in my case and just overall doesn’t feel right.

So I started to change the game to be polygonal instead of grid-based (or at least have the entities moving freely within a grid-based dungeon). This led me to decide that A* wasn’t really going to work well for all the enemies in the maze, both because it’s expensive to run on like 100+ entities every frame, and because even if the entities are free-moving they can only have as little granularity as the A* algorithm has. It also occurred to me that it doesn’t necessarily make sense that enemies halfway across the maze can just magically find exactly how to get to you.

So I decided to try out a steering algorithm. It only took me a couple hours to get to this point and think it works really well. Basically, each entity sends out 3 raycasts each frame, one in front and two at 45º angles. If the front cast hits anything, the entity will begin decelerating. If any of the side ones hit anything, it will turn in the opposite direction. If both side ones hit anything, it turns towards whichever is furthest from the wall. In the off chance everything is equidistant, it will use its “turn tendency” which gets recalculated every time it finds a clear path.

There are two options here as well. One makes everything look much more natural but allows for the rare chance of the entity getting stuck in a corner turning left and right until the end of eternity. The other makes sometimes greater than 180º turns (so looks weird) but it will never get stuck. I decided to go with the former option. The difference in terms of code is simple - for the latter, once the entity starts turning it must keep turning in that direction until it is completely free and clear. In the former, the entity may recalculate direction any time either its left or right raycast is clear.

One last thing - if the entity gets within a certain radius, it completely stops. This disallows overlapping collisions.

Oh wait, I also added a very simple weighting system that’s not fully hooked up, where as an entity exists in a grid area it adds to the total cost of that space. This makes it desire going towards lower cost spaces, which encourages a sort of patrol behavior.

I’ve also recently added some rudimentary attack logic (not in this demo) and will be improving the cost logic to make it really work. Part of doing that will be by adding a “target” location that makes the cost of the target 0 and nearby spaces like 0.5, causing the entity to always want to hang out there.

Anyway, here is a video of it in action. If you full screen it, you can see very small indicators of the front of the entities.

I’ll keep posting videos as I improve it, and if anyone wants the source let me know (but it’s in Unity C#).

#2

I am liking it so far!

One thing that caught my eye is that it appears that they speed up when they get into a corridor straight aways. they start accelerating. I feel that their rays should get longer as they are moving faster or in the big open areas because they sometimes seem to smack right into a wall because the ray wasnt long enough. I am not sure how much youve tweaked it to current size though.

#3

This looks good. I noticed two things that will hopefully make it better,

  1. There was a dude who got stuck in a narrow hallway and never turned enough to see his escape, he kept oscillating to the left and right but couldn’t get out. At some point, you might want to trigger a full 360 check if he can’t find a way to move after a period of time.

  2. I think they need to have a faster avoidance reaction. It seemed like a lot of time (especially when coming to the end of hallways), that they’d try to start turning but wouldn’t slow down enough so they’d run into the obstacle and then turn against the wall or other bot before continuing their path. Are you familiar with the work on “boids” here? http://www.red3d.com/cwr/boids/

#4

All great suggestions, thanks guys. I added ray extension which definitely helps and also a timer so that if they haven’t had a free view for too long they’ll just keep turning until they see one. Both ideas work very well.

I am familiar with boids, I based this implementation on a rough memory of it. Part of the issue that you’re pointing out is that they have a constant turn speed and not a long enough ray when they are at full speed. I also didn’t do any acceleration calculation in terms of deciding how quickly they should slow down - it’s just a constant amount of they see an obstacle. The result is that they sometimes slow down too quickly and sometimes too slowly. I think I’ll tweak this at some point in the future in order to improve it.

I’ve updated it to have animated models that punch at each other if they get nearby and incorporates some of the ideas you guys mentioned. I’ll throw that into a video sometime soon.

#5

Cool it be used as a pathfinding for driving car along a road? Always wonder how to do AI in driving game.

#6

Of what my limited knowledge knows. one of a few things usually occur.

There is a premade polyline or path around the track that the cars try to always get close to or follow perfectly.(i.e. if you bump them, they will try to get back closest to this. (with maybe a slight random offset from center for a little variation)(think of google maps/streets)

probably a system not to different from the above example, perhaps with more rays(depending on how car/settings)

They use a waypoint type system where there is a ton of waypoints that they are always trying to drive to and just have a basic pathfinding to go around misc obstacles(i.e. your car or others)

Earlier car games often cheated and the A.I. could sometimes make turns impossible by player.
You could record an actual person playing and then push those saved movements into the A.I. with some minor adjustments for player bumping into them. (i.e. if nothing interfere it follows recorded drive path perfectly) if it gets bumped off, A.I. tries to get it back on path asap. (also margin of error, will still follow movements/recording if slightly offset from precise location.

Most newer/newset games use a combination of all the above and some of them I think even have advanced decision making algorithms/abilities to handle dynamically changing landscapes and a lot of A.I. cars/pedestrians…

#7

See namrog’s answer, but yeah, if you use a system kind of like this and also have better weights (so it would rather be on the track than in the open field) and also a way to get it to keep moving around the track. The system I have here is more or less random, which suits my purposes but wouldn’t in a lot of cases. Also I can get away with only 3 rays because I always move towards the forward of the object, meaning there is no true momentum. In a car game this just wouldn’t work, so you would need to either send more rays or just send them along the direction you’re actually moving. I might send out 3 along the forward to help future decisions and 3 in the direction I’m moving to deal with collisions and the like.

#8

I once read about a game with boats where they used flowfields successfully. With flowfields you don’t need any rays but you need some kind of distance sorter if you have many vehicles/obstacles.
Another name for flowfields is perhaps potential fields.

#9

Cool stuff, the movement looks very very natural.

Keep it up!