I'm going for only single-ship-pathfinding, not large groups. You're right, that would make a huge difference in what kinds of pathfinding I could use.
Have you already tried some other techniques whether they work for you?
I was first going to start with A*, but decided that wasn't the way to go, because of very large differences in the sizes of my ships (a large carrier vs a small fighter), where there'd be too many moving obstacles of varying sizes. So instead, I tried doing only obstacle avoidance. This was a pretty simple method:
-Trace from my position to the destination point.
-If something's in the way, then take the vector from the object's position to the target vector, add it to the targetvector (so now I have a position somewhere outside the round asteroid) and restart the process with that new point.
-Additionally, I had 4 (or 8) traces going out from the ship, towards top, bottom and the sides, checking if the ship was getting too close to any geometry there, and if it was, I rotated the velocity a little to get away from those objects.
This has its disatvantages though. For one thing, this only takes the obstacle's position into account, not its velocity (If the obstacle is a ship, then it could fly straight where I'm going. A human player would move out of the way, but then the bot-player wouldn't - cause the destination is straight ahead and there's nothing, yet, in the way - and they'd probably collide).
So I left that test alone and concentraded on multiplayer-code.
I also posted here about 2 years ago or so to see if anyone knew any good solution for 3d-pathfinding and obstacle avoidance, but didn't find any good solutions, if I remember correctly.
So, I did a little more thinking (this is all very basic, of course, I only had this idea yesterday and don't even know yet whether proper AI will make it into the game). This is the current Idea:
- I'm not going to use flowcharts as shown in the image, because I don't actually need them in empty space. Instead I'll have a "flowchart" that is only present around asteroids. At startup of the level each asteroids writes its position and the flow-nodes around it into the flowchart. This will be used for basic movement: when a ship reaches such a node it'll follow the flow around the asteroid.
- The second flowchart will be made by the moving objects. Relative to the ship, they will always stay the same.
- The resulting movement will be taking into account both the ship flowchart and the static flowchart.
- The advantage is that the flowcharts don't actually have to be changed.
I have no Idea if this will work. But it seems to make more sense than anything I've thought of so far. I have two basic problems (that I can think of atm):
- How do I represent a node in space? How can the ship know which node to follow? It can't constantly check all nodes in both fields and see how close it is to them...
- What happens when mutliple nodes "collide"? Meaning what happens when there's two contradicting nodes - one from the static and one from the dynamic field - at the same position?
Just brainstorming....
I think in this way this isn't so bad for single-entity-units (vs large groups). Maybe I shouldn't call it "flowchart" anymore though. More like "direction Nodes"...?
Any ideas on this method?
