• 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
BenS1

Path Finding for Complex Vehicles

4 posts in this topic

Hi

I'm developing a RTS game where the player can create their own units (Vehicles) in game. This means that there is potentially massively differences between the different units in the game.

For example, there may be a big difference in unit sizes, such as one type of unit that is 3m x 2m x 2m, and nother that is 100m x 100m x 20m and another that is 80m x 10m x 10m etc.

Its not onyl sizes that may differ either, there are other things such as the weight, power, the actual way its driven (e.g. does it have wheels or catapilar tracks etc).

All these things effect which parts of the terrain the units can drive on. For example, there may be a narrow canyon that a 3x2x2 unit can travel down but a larger unit can't. Or there may be a steep incline that a powerful or light vehicle with catapilar tracks can get up but other vehicles cannot, etc.

This is a bit problem for pathfinding.... I've used A* successfully in the past but it seems like there are just too many variables for me to be able to use it here.

If size was the only variable then I could create 8 different A* maps, one for 1x1 units, the next for 2x2 units, next for 4x4 etc, up to 256m x 256m units, but that assumes all units are square and doesn't help with other variables such as weight, power, drivetrain etc.

Is there another type of pathfinding algorithm that is better suited?

The only other solution I can think of is to use A* but to calculate the node to node costs (And indeed whether its even possible to get from one node to another) in realtime. This would potentially be computationally expensive but probably do-able.

Any other suggestions?

Thanks in advance.

Ben
0

Share this post


Link to post
Share on other sites
At each node expantion step of your A* loop: filter out neighbour nodes that do not pass your vehicle requirements, that is, consider them non-reachable even if they actually are connected (adjacent) to your current node

There are ways to speed those validation computations up by precalculating data at map generation time.

Things you can store per cell:
- Distance to closest static obstacle, AKA, largest unit size that can stay on the cell.
- Cell slope.
- Average height difference at each edge, AKA, stair-step height when crossing to that neighbour. Useful for determining if legged entities can consider that cell accesible or not.
-Terrain type.

If any of those conditions fail to meet your vehicle requirements for that particular adjacent cell then consider it not connected to the node you are evaluating at that point in your A* search.
2

Share this post


Link to post
Share on other sites
Nigo beat me to it. I've been doing some pondering on similar matters (but creature rather than vehicle based). If you make some basic assumptions, e.g. rectangular, a small set of locomotion possibilities, don't allow 3 point turns, the problem can be manageable. Storing the distance to the closest obstacle allows accommodating vehicle width by only considering nodes with distance >= width / 2. Essentially you just need to call a custom function each time you evaluate an open node to filter possibilities.

You could also store some state at each node, e.g. vehicle orientation and speed. This does break the optimality of A* if you handle it wrong, but generally vehicles aren't used in super constrained environments, so an acceptable solution would still be found. If you can quantize your states (e.g. 8 directions and 3 speeds) you could add another dimension to your A* graph which would allow basic problem solving, e.g. cover the same ground multiple times to achieve a goal like 3 point turns or jumping. Alternately you could tag difficult places on your map or detect them automatically and use canned techniques to solve problems, e.g. add a temporary node from your current position to behind you that executes a 3 point turn with cost x.
1

Share this post


Link to post
Share on other sites
Thanks both for your replies.

I think what you're saying will work.

The only thing to mention is with reference to "Distance to closest static obstacle" is that its not quite that simple as its not clear what an obstacle is. For example, something that is an obstacle for a 3m x 3m vehicle may not be considered an obstacle for a 100m x 100m vehicle that can just drive over it.

But in general I think what you're saying works.... I'll just have to calculate the costs and node connectivity at runtime as opposed to having a nice fast precalculated map of data.

Thanks
Ben
0

Share this post


Link to post
Share on other sites
one method i came up with when i was working on variable sized agents in A* was to allow the unit to exist on several nodes at once, and pick one of the node's to be the center/movement controlled node(generally it was the center node, but you can determine this however you'd like). when the centeral node was evaluating the next node to move to, it'd check all the node's that the agent will reside on, to ensure that they are legal. it's possible to speed this up since with agents that sit on more than 4 square nodes would already be occupying the many of the nodes.

for example:
a unit that sits on 6x6 nodes, moves exactly one node to the left, would only have to evaluate 6 nodes for legal movement, as the rest of the 5x6 we were already sitting on, so they must still in theory be legal, a diagnal node would require evaluating 11 nodes, as the other 5x5 nodes are were we used to be sitting.

their are probably potentials for it to be sped up more, but this imo, created a decent result for variable sized units on a fixed sized grid.

as for problem's with terrain movement, that's as nigo said, simple filter's applied to checking if the move is legal.
0

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