• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0

Pathfinding in a space-based RTS game

6 posts in this topic


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.

[b]Description of the game/problem:[/b]
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.

[b]What I've come up with
[/b]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.

[b]This is where YOU come in
[/b]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!

Share this post

Link to post
Share on other sites
Once you've plotted your ideal route, put tags along the route into the oct/quad tree that you're using for things like culling. The tags know when the unit is expecting to be at that point.

Each of the tags "watches" bits of the routes. As you create objects and move them around inside the space, they can notify routes that they're blocking and unblocking them. The ship owning the route can decide if it's something it needs to think about now, or later. If the obstruction goes away later, then the ship need never have done anything.

The same thing can be used later on for sensor systems watching for intruders and so on.

When you plot a route, you can check for potential collisions a long way off; displacing your route if you find something else there, kicking them out if you think you should have priority.

Planetary orbits are collections of tags into the tree which know about the orbital period.

If something intervenes in the route and it's quite close, that's the trigger for doing a local replanning.

Solving the "who moves" is easy. Serial number every unit. Small units give way to large units. In case of a tie in sizes, highest serial number wins.

Share this post

Link to post
Share on other sites
Thanks for your replies, they are very useful.

I have been researching some more and have indeed decided to go with steering mechanisms like flocking. I'm reading everything I can on this, and am implementing it. So far, I've only got cohesion working, which was very straight-forward. A (slightly) detailed explanation of the steering forces you mentioned would be of great help to me. So far, any papers I found on the techniques leave a lot to the imagination.

I also think the influence maps would be the best solution in this scenario. Truly blocked areas are uncommon, and the C-shape you mentioned is very unlikely to occur for any objects other than ships, which are already taken care of by the aforementioned steering mechanisms (at least for friendly units, I'm not sure yet how to react to enemy units, but to be honest I think it might be best to tackle this problem later).

I think I have an idea of how influence maps would work, but again I wouldn't mind you explaining the concept a bit.

I really like the reactive system, instead of using a predictive system that seems overkill. I'm going to have to see if it will be easy to implement this in the client-server architecture, to see how much work will need to be done on the server to achieve synchronization, but at least for offline purposes it seems to be exactly what I was intuitively looking for. Our game will use a fog of war system that will only take into account entities that are close to your own planets/ships, so going with a reactive system makes sense.

I've gotten some good ideas from your post as well. Right now it seems I'll be going in a direction where not everything you said will be applicable anymore, but there are some hints in your post that I find interesting, such as 'small' units giving way to bigger ones. I've also not thought of using my quadtree for keeping track of this info, which is something I will definetly keep in mind!

Share this post

Link to post
Share on other sites
@AIDaveMark: Thanks, I found the URL myself as well and was already studying it, but it's nice to mention it in this topic in case other people end up here.

@ApochPiQ: Thanks for the explanations. I've already implemented a few of these behaviours. I've implemented seek (=Follow with or without arrival, depending on if you are moving to a desired, static position or if you are chasing an enemy ship), and flocking (separation, alignment, cohesion). What is unclear to me is how Grouping and Separation are different from resp. cohesion and seperation as in flocking. From your explanation I can't really deduce if it's a separate type of behaviour, or the same thing (maybe with different parameters).

When you are talking about Grouping, you do mention a problem that I haven't solved yet: When I have multiple units selected and I make them move to a desired location, they don't end up in a relaxed state because flocking (or even basic collision response) prevents them from reaching the exact target location, so they keep moving toward it, trying to push eachother away (sorry, I love applying semantics to emergent behaviour).

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  
Followers 0