Hello everyone,
We just finished our first project Trace Invaders, and we’re looking to start a new project which is a space combat game complete with enemy AI’s. The biggest problem I’ve run across was accounting for obstacles in between the enemy and the player. I was trying to find some resources on how to code something like that. I’ve come across a lot of references to A* and Dijkstra’s, but I don’t understand how that can apply to 3-Dimensional space with no nodes/tiles. Does anyone have any useful links or resources they can point me towards?
Or else come up with your own (what I would recommend) - the best way to do this is:
Start off your AI script with just a simple “look at and shoot always”
Then go for “only look at and shoot if he’s alerted”
When is he alerted? i.e. when the player walks in front of him or near him?
Now what happens if don’t exactly come near him, but close enough that he hears a noise?
What if the player starts shooting back? He has to find cover! Move over to the closest waypoint of a specific set of waypoints (which would be behind walls)
Now the player’s not moving - he’s staying in cover! What do you do? Maybe approach him? Or call your teammates?
Finally, what if there are other teammates around you? They would want to know when you are alerted! (send a signal to all objects maybe)
Doing it step - by - step is a lot easier then copying and pasting someone else’s code. (or maybe you just need to modify that code )
I suppose my real question then is, is it still viable to use node based pathfinding in a situation with complete 3-dimensional mobility. Think Starfox 64 (All range mode).
Many common pathfinding algorithms like A* use weighted nodes to determine possible paths to an objective. This works very well in 2D space, but I was wondering how it is done in 3D? Or if it is even done in 3D like that? I’m just curious as to what the common consensus is about it. I’m going to be buying a book soon about the topic, but I really want to start learning ASAP.
A* is a generic solver. It’s used a lot for 2D/grid based stuff, so most of the implementations are geared towards that, but it could be used for anything from 3D space or even generic problem solving. Check out Micropather (http://www.grinninglizard.com/MicroPather/). It’s implementation is pretty generic.
Pathfinding is probably not used very often for space games though, except maybe for finding paths between warp gates or something. Just because there’s a lot of chunks when dealing with 3D, so you have to store a bunch more path finding data. Best bet would likely be dealing with it using raycasting and steering.
Consider using something similar to OpenSteer. Here it’s called UnitySteer. It is a set of tools for Unity that were developed to do a few different behaviors similar to what you want. Obstacle avoidance, chasing fleeing and such, all in there.
Glad I am not the only one fighting with this… I the post on the subject years ago but it has all ways been a thorn in my side. I am getting to the point in my project that I am going to work the issue once more and see what I can come up with. I tried to use unitysteer but never could get it to work right with the scale of my space ships… I wish someone had a package like Rain for space ships that did not depend on nav meshes…
3D pathfinding is really no different to 2D. You just have more space to work with. The general principles of A* will still work. As do the general principles of steering behaviours.
You can do dynamic 3D path finding by
Setting up a series of nodes around each collider
Get a list of nodes
Using raycasting to determine passability between each node
Run the resulting network through an A* algorithm to get the path
I have no current need for 3D path finding. But I might build something one day for kicks and giggles.
I have played with Rain but not A*. Last night I worked on getting the Alien ships collecting and being able to destroy them. To night I plan on working on getting my robot ships up to par with the Alien ships with the new scrip and if I have time teach them to hate each other. At this time the ships have no object avoidance at all.
What makes 3D harder is with 2D you have 2 choices Left and Right, and most objects or stationary (like walls). In space now you can go any direction to get around and also you now have 2 objects that are moving trying to avoid each other.
I personally am thinking about doing racast or using a trigger sphere around the ships. I all ready plan on dropping Rain in for the NPC (non ships). Dropping A* may not be a good idea considering the project is all ready huge… lol
For A* applied to 3D settings, search for cubic nodes, or cubic tiles. I’ve already read papers on that. It is not that uncommon. However, I don’t think it is practical for a space game. The reason being that space has a lot of space. Which means, the number of tridimensional tiles increase too fast, making the array that store tiles to become too big memory-wise and therefore the A* too slow performance-wise.
I think what you need is steer behavior techniques, i.e. approaches that only are turned on to maneuver around obstacles when obstacles are close enough. For a very advanced technique, search for RVO2.
)