Original Post
Hi,
In a game I'm developing, I am hitting the stage where I need to implement pathfinding. I've been doing research on different methods of pathfinding, to see what would work best in my situation. However, most, if not all articles I found assume different game types with problems that aren't present in mine. I have a feeling I can get away with a fairly simple method of pathfinding, and don't need a lot of the overhead traditional pathfinding methods introduce.
This topic is intended to discuss theory, but taking in mind implementational details such as ease of implementation, and performance.
Description of the game/problem:
This game is essentially an RTS, rendered in 3D but with all the game logic in 2D. (I think this is called 2.5D?) Meaning, space ships, planets, etc. move over the X, Y-plane. Meshes are 3D and the camera is fully free in 3 dimensions. For pathfinding, I will thus be working in 2D.
The game takes place online only. The client application receives all the world, ship and other data from the server, and constructs the world out of it dynamically. The universe is divided into solar systems, and the player will only know about the solar systems near to him. So basically, there's no advance knowledge when the game is started, so I can't pre-fabricate navigation layers, waypoint graphs, or anything. It all needs to be done in real time.
Every object that needs to be taken into account will have an X,Y-position, and a radius (spherical collision). The player can click on a location in space with one or multiple units selected, in order to make the units move to that position. Thus, a unit will set a destination. The server will be notified and has to be able to figure out the path the unit is moving along to predict it's position at a given time, until the destination is reached. The first issue occurs here: Should the server be able to calculate the path the unit will take, or should this be done client-side only, after which the necessary data points are all sent to the server? The issue arises because the server has full knowledge of any (enemy) units that might get in the way of a path, yet the player might not know about these ships (and if that's the case, we don't want to take those ships into account because it would give the player information that it shouldn't have).
Stepping away from the client-server problem, the real issue why I created this topic is the pathfinding algorithm itself. I've studied AI for a few years, and I've read a number of pathfinding articles recently, but I feel most of the solutions are overkill or just not well suited, given the relative simplicity we can assume (spherical objects, relatively small amount of objects in the game world), and on the other hand the dynamic nature of the world and everything in it (everything moves, planets, units, and other entities). Most algorithms use waypoints (in the A* sense of the term) or a navigation layer, both of which I don't think are particularly suitable for this game. So I set everything I knew about pathfinding overboard and decided to see if I could design a system that made sense for this particular game.
What I've come up with
Not yet taking into account moving multiple units at once (which will introduce formations, taking into account different unit properties such as velocity and turn speed, and other variables that make matters more complicated), the problem seems easy. Given a position and a destination, just calculate the straight line between the two. Scan along this line for collisions, taking into account the radius of the ship that's moving and the radius of objects that are checked for collision. If a collision is detected, project the position (not taking into account radius) of the collider onto the traceline, create a waypoint there, and move the waypoint away from the collider's position just far enough so the moving unit can go around it. Check for the new line parts if no new collisions appear, and keep repeating until we've got a proper trajectory. Follow this trajectory (which could be sent to the server as a number of destinations, so the server doesn't have to do its own pathfinding).
A number of things aren't taken into account in this simple scenario. First of all, we don't have any predictive value. All that can be done is check if there's no obstacles in the way at the time when the path is calculated. Since all obstacles are dynamic, chances are that obstacles will appear down the line later on. This will be especially true when fleets are engaged in battle, where there could be as many as fifty-or-so ships flying around quite near eachother. So, I'd somehow have to construct a mapping that not only describes the position of a given unit, but also the time at which the unit is in the given position. In itself not a hard task, but scanning this list for collisions when creating a path from a to b might become complicated and slow if not done properly. At the very least I'll need to use some kind of hash mapping to make this feasible.
Second, when two objects are planning a path, and run into eachother at some point, we wouldn't want both objects to alter their route with the logic above, since their alterations will often make them run into eachother again. How will I determine which object derives from it's ideal path, or will they both do it? Will one object slow down to a stop to let the other pass? (Note that this is very costly in space, the ships will accelerate slowly and ideally always keep moving).
Third, objects like planets, although dynamic, should obviously never stray from their defined paths. A planet isn't moving fast, but in an ongoing world, there will be occassions when a planet is about to collide into a ship that's just sitting there, and the ship should see this collision coming and move out of the way autonomically.
Fourth, since units are not completely free in their movement (they can't slow down or get to full velocity instantly, nor can they turn an infinite amount in finite time), when additional waypoints are introduced, the whole trajectory of the unit will have to be smoothed out to make sure the unit can actually follow the path. This also introduced the fifth (and last I can think of) problem (more of a constraint): though a certain path may be the shortest possible, given the parameters of the unit it might still be non-optimal because it's too slow (if a unit has to come to a full stop five times, it will take much longer than when the unit can move over a path that is longer, but requires no slowing down at all). Ideally, the time it takes to complete the path is taken into account in the search for one.
This is where YOU come in
Given this problem description, I'm looking for either/both solutions to the described problems, or existing pathfinding algorithms that match the properties of this game as well as possible. Also I'm interested to see if you can come up with problems that I've overlooked, and need to take into account.
Thanks in advance for any help!
In a game I'm developing, I am hitting the stage where I need to implement pathfinding. I've been doing research on different methods of pathfinding, to see what would work best in my situation. However, most, if not all articles I found assume different game types with problems that aren't present in mine. I have a feeling I can get away with a fairly simple method of pathfinding, and don't need a lot of the overhead traditional pathfinding methods introduce.
This topic is intended to discuss theory, but taking in mind implementational details such as ease of implementation, and performance.
Description of the game/problem:
This game is essentially an RTS, rendered in 3D but with all the game logic in 2D. (I think this is called 2.5D?) Meaning, space ships, planets, etc. move over the X, Y-plane. Meshes are 3D and the camera is fully free in 3 dimensions. For pathfinding, I will thus be working in 2D.
The game takes place online only. The client application receives all the world, ship and other data from the server, and constructs the world out of it dynamically. The universe is divided into solar systems, and the player will only know about the solar systems near to him. So basically, there's no advance knowledge when the game is started, so I can't pre-fabricate navigation layers, waypoint graphs, or anything. It all needs to be done in real time.
Every object that needs to be taken into account will have an X,Y-position, and a radius (spherical collision). The player can click on a location in space with one or multiple units selected, in order to make the units move to that position. Thus, a unit will set a destination. The server will be notified and has to be able to figure out the path the unit is moving along to predict it's position at a given time, until the destination is reached. The first issue occurs here: Should the server be able to calculate the path the unit will take, or should this be done client-side only, after which the necessary data points are all sent to the server? The issue arises because the server has full knowledge of any (enemy) units that might get in the way of a path, yet the player might not know about these ships (and if that's the case, we don't want to take those ships into account because it would give the player information that it shouldn't have).
Stepping away from the client-server problem, the real issue why I created this topic is the pathfinding algorithm itself. I've studied AI for a few years, and I've read a number of pathfinding articles recently, but I feel most of the solutions are overkill or just not well suited, given the relative simplicity we can assume (spherical objects, relatively small amount of objects in the game world), and on the other hand the dynamic nature of the world and everything in it (everything moves, planets, units, and other entities). Most algorithms use waypoints (in the A* sense of the term) or a navigation layer, both of which I don't think are particularly suitable for this game. So I set everything I knew about pathfinding overboard and decided to see if I could design a system that made sense for this particular game.
What I've come up with
Not yet taking into account moving multiple units at once (which will introduce formations, taking into account different unit properties such as velocity and turn speed, and other variables that make matters more complicated), the problem seems easy. Given a position and a destination, just calculate the straight line between the two. Scan along this line for collisions, taking into account the radius of the ship that's moving and the radius of objects that are checked for collision. If a collision is detected, project the position (not taking into account radius) of the collider onto the traceline, create a waypoint there, and move the waypoint away from the collider's position just far enough so the moving unit can go around it. Check for the new line parts if no new collisions appear, and keep repeating until we've got a proper trajectory. Follow this trajectory (which could be sent to the server as a number of destinations, so the server doesn't have to do its own pathfinding).
A number of things aren't taken into account in this simple scenario. First of all, we don't have any predictive value. All that can be done is check if there's no obstacles in the way at the time when the path is calculated. Since all obstacles are dynamic, chances are that obstacles will appear down the line later on. This will be especially true when fleets are engaged in battle, where there could be as many as fifty-or-so ships flying around quite near eachother. So, I'd somehow have to construct a mapping that not only describes the position of a given unit, but also the time at which the unit is in the given position. In itself not a hard task, but scanning this list for collisions when creating a path from a to b might become complicated and slow if not done properly. At the very least I'll need to use some kind of hash mapping to make this feasible.
Second, when two objects are planning a path, and run into eachother at some point, we wouldn't want both objects to alter their route with the logic above, since their alterations will often make them run into eachother again. How will I determine which object derives from it's ideal path, or will they both do it? Will one object slow down to a stop to let the other pass? (Note that this is very costly in space, the ships will accelerate slowly and ideally always keep moving).
Third, objects like planets, although dynamic, should obviously never stray from their defined paths. A planet isn't moving fast, but in an ongoing world, there will be occassions when a planet is about to collide into a ship that's just sitting there, and the ship should see this collision coming and move out of the way autonomically.
Fourth, since units are not completely free in their movement (they can't slow down or get to full velocity instantly, nor can they turn an infinite amount in finite time), when additional waypoints are introduced, the whole trajectory of the unit will have to be smoothed out to make sure the unit can actually follow the path. This also introduced the fifth (and last I can think of) problem (more of a constraint): though a certain path may be the shortest possible, given the parameters of the unit it might still be non-optimal because it's too slow (if a unit has to come to a full stop five times, it will take much longer than when the unit can move over a path that is longer, but requires no slowing down at all). Ideally, the time it takes to complete the path is taken into account in the search for one.
This is where YOU come in
Given this problem description, I'm looking for either/both solutions to the described problems, or existing pathfinding algorithms that match the properties of this game as well as possible. Also I'm interested to see if you can come up with problems that I've overlooked, and need to take into account.
Thanks in advance for any help!
