I have developed a simple Implementation of Grid-Based Navigation for my jME-Game and I decided that it would may be worth to share it later, as there is no sucht thing right now (or I didn’t found it ;))
It currently provides only very basic functionality and cannot really be used in other games, as it uses some game-special things. But in the long term I plan to extend the functionality and make the code more generic.
For those who don’t know what Grid-Based Navigation is used for:
It uses small simple rectangles to cover the map. Each specific rectangle can either be walkable or not. In contrary to NavMesh-based Navigation this “walkable-information” can be changed a lot easier at runtime.
This is also the/one main reason to use it: In games where the map changes very often (e.g. in RTS-games).
What I have done until now:
Generation of the grid-map
Basic functionality to change the grid-map at runtime
Pathfinding on the grid-map and basic optimizing/smoothing of it
As I said previously the number of features will grow as time goes on (we’ll see how fast…).
Why do I tell you this now?
For the pure knowledge. If anybody needs this in the future he can decide to wait for my implementation.
I also want to invite you to tell me what features you would like to have there. I can’t guarantee anything, but maybe I can do it for you or tell you how you could do it.
I won’t make any promises I can’t keep, but my personal aim is to have something working for you this year.
So if you have any questions on the “project” just ask it. I hope I can answer them
And tell me what features you would like to see!
For later: “tactical A star” (pathfinding with tactics)
For now:
have squares that are not only “walkable” or “free” but also “destroyable” (walls, buildings, trees).
have more than one kind of terrain: walkable (ground), swimmable (shallow), walkable mountain (infantry only), swimmable (deep), walkable sand (tank and infantry only), walkable swamp (infantry and hovercraft), …
have markers for danger: (mines, known), beacon (“there is heavy enemy presence here”, how much?) in preparation of the “tactical A star” algorithm
group navigation
allied troops navigation
priority for who may go first
ability for A.I. of standing units to make the path free for moving units (sorted by priority)
Just some of the things that come to my mind…
I have a project (fully designed and on my todo list) that would use such a system. So if your system is good and free, then I will maybe take a look at it when I start to make that game. But it’s a war game and according to my new policy the priority for such stuff might be lower in the future - and I might never make that game in the end…
I had to build an custom solution for my game Ant Maze 3D for moviment in grid :
Since I am moving the char based on an speed an fps, and I need to arrive at the center of the cell, and its running on android, sometimes because of the abrubt changes on fps it may bug crossing walls and crashing the game.
The only way I found to fix it was to fsync and to ignore very slow fps…
Did you make any solution for this problem ?
This will be possible, but you will have to handle the “destruction” by yourself. As I said it will be possible to change the state of a grid after generation. So if you have a tree that gets destroyed you just set the corresponding grid walkable.
This is a good idea. It should be no problem to add something like “movement cost” to the grids.
This maybe could also be done with the movement costs?
This is definitely something I want to have. No promises though when this will be.
I don’t understand, what you mean here
Same
Again
Tactial A star: You will have to explain this a bit more too. But if my intention, what you mean is right, this would be very game specific.
My system will be definitely free, if it will be good, we’ll need to see…
If I got what you wanted to say, your problem is not directly tied to the pathfinding but to walk the path later.
My system will just handle the pathfinding for you and will give you a path with multiple waypoints. What you do with this path is up to you.
Also I haven’t really said this before: Currently my system is working with a world which only uses the grids for pathfinding. Units can move freely on the area. I’ll see how the system can support both options:
Movement only allowed on given paths from grid to grid
It’s more than that: You can’t move across, but you plan to move across after you destroyed the obstacle - so it’s between “blocked” and “free” (or both actually).
The preparation for “tactical A star” would include calculating if it’s worth to destroy the building or wall or take a different route. Calculation would include nearby helpers that want to take a similar route.
Of course, this could be expressed by “movement cost” (which is the core of “A star” or “tactical A star” algorithms). But it’s not that simple - imagine the enemy can repair buildings or you don’t want to destroy walls, buildings, bridges, etc. because you need them for your own purpose later.
No, you must distinguish types of travellers / types of units.
Example: It depends, if you are: ground-based, water-based or air-based. And infantry can climb mountains which tanks cant. Ships can swim, big ships can’t swim in shallow water. Tanks can not swim. Amphibious vehicles like hovercraft can swim, but not climb. And so on…
“Movement cost” won’t work. The traveller / unit can either move across or not - based on what type of the traveller / unit is trying to move across.
No… you need to be able to place beacons (virtual warning signs) so that the A.I. can calculate a different route (e.g. “you can move over this unstable ground but there is a 10 percent chance that your mars rover will crash” or “there are mines there - chances are high that it detonates, which will reduce the number of mines on this grid space by 1”).
Doesn’t really matter … you will find out later.
Which techniques are you planning to implement? Did you do some research?
And … you can start simple - so my thoughts are pretty advanced things.
To do what you want to do you can keep things low and just make the basic things first.
Most problematic will be point (7.) - your A.I. travellers blocking each other’s way and getting stuck…
It seems there were some missunderstandings on both sides
I already have a basically working pathfinding system, but it’s currently tied closely to my game.
I now understand most of your “feature whishes” and I’ll have to see which of them I’ll be able to implement in my implementation. Some of them seem really specific, so it may not be good to implement them in a generic pathfinding-solution. But I/we will have to see about that
I know that most of your suggestions are to be done later in the development. But I think it’s a good idea to know about future visions when you make the basic design.
Techniques: I currently use a part of the Java-part of CritterAI to generate the Grid-Map. The pathfinder uses the Theta*-Algorithm to calulate a Path. It’s basically derivate of the A*-Algo. Is this what you meant with Techniques?
No problem. I was just trying to be helpful and point you to the possible rabbit holes that come during later steps of development.
I sometimes tend to overthink things. If you want to get your task done, you better do it like the “agile hackers” - building up tools as iterations of rapid prototypes with a “bottom up” approach is what they do. I guess it’s better to not overthink things and proceed in several small versions - one step at a time. There is always the todo list where you can write down ideas for later (my todo list keeps getting longer and longer, but many things will never be done - I just write down ideas so that I don’t forget them and so that there is new space for creative ideas in my head).
And that is exactly why I posted the project this early. Thank you!
In on lecture I’m hearing we learn something about agile development and development strategies in general. I’ll try to use some of the techniques I learned there and see if it works
One of the techniques is development in small steps as you mentioned. But I still think that you need the bigger picture when you’re thinking about the overall design, otherwise it could happen that your desing does not work with some later “extensions”.
