I’m using LibGDX’s pathfinding which can be found here:
This is what I was able to get so far, but it all looks very mechanical, and not sure where to go from here. This is just basic A* pathfinding. How can I make it look more realistic? What do I do after adding the pathfinding? Also I do want to make it multiplayer so what are some things I also have to look out for when working on this? So basically what are things that I should look into?
Just an update I added Libgdx’s pathsmoother, is there anything else I should look into? Also it takes an average of 2.5 ms to calculate that path (each tile width is 16x16) is that bad?
2.5 seconds is unacceptable, have you tried LibGDXs IndexedAStarPathfinder ?
It should be a little bit faster than the vanilla version: https://github.com/libgdx/gdx-ai/wiki/Indexed-A*
I think you’ll need to run this calculation in a separate worker thread or do the pathfinding in small chunks over multiple frames (i don’t know if LibGDXs pathfinding allows this hmm) if you want to use LibGDXs API AND have a fluid game.
Or you could use a different pathfinding library (there are many out there) that is actually made for large open spaces and doesn’t use individual objects for nodes, A* isn’t optimal for this at all.
[quote]I do want to make it multiplayer so what are some things I also have to look out for when working on this? So basically what are things that I should look into?
[/quote]
That’s a very broad question, just make sure you plan ahead or it’ll be a huge mess.
And read some articles on network programming.
Can you recommend any path algorithms for larger spaces?
There is no magic bullet pathfinding for larger spaces.
A* is about as good as it gets for the typical search space graph. Other algorithms might work better in specific cases. (when there are many dead ends for example)
In some cases, paths can also be precalculated beforehand, or reused paths from former searches.
Its more important define what you mean by large space, and how you define it.
You should try to get a hierarchy working, to first do a long range path search through the general areas (separate graph), and then a more detailed within the specific location (starting area, destination area).
An example is how you would travel personally long distances using a map. You would first plant your trip according to the large highway network or air transport. And then when in town (using a local map), look for the small streets, to get to the house. And THEN how to walk through the garden-door and avoid the neighbors dog.
Its a complicated topic, hence there are a lot of tutorials for it.
The following (and separate) step is how to traverse the calculated path.
That depends a lot of how your actor can move, and what happens when there are dynamic obstacles on the way (calculate a whole new path, or have the ability to pass smaller obstacles)
For larger spaces I would recommend you look into the HPA* Algorithm (Hierarchical Pathfinding A*), this speeds up the time needed for calculating the search massively by firstly performing a quick broad A* search on the map and then small chunks of a finer A* as you move along the broad path.
For speeding up the actual A* search you will want to look into applying a ‘Jump Point Search’ to it.
Try profiling your code. I’m sure you could reduce the time by 80 percent after finding the bottleneck.
You could do away with tiles, simple maps like the one you showed could be done with polygons. The only benefit of tiles is that you can dodge other units, but when pathfinding is so slow with tiles that becomes hard.
Sorry guys I was wrong it’s 2.5 ms, not 2.5 seconds. So I guess that’s not as bad? I still want to get it more down, since a lot of paths would be generated.
Also from my understanding, the bigger the map, the more time it would take to find paths due to all the nodes. Could anyone explain to me how regions / chunks should be handled? This way it only loads paths in that specific region, while still being able to process the entire game world (as from my understanding that would also affect rendering since its more tiles to render).
2.5 ms sounds ok if you dont have too many actors, but you might be able to optimize the path-search more. (at 60 fps a frame is 16 ms long)
Best is to post a picture of your gameworld (passable/blocked area) to see what aproach works best here.
And also if your maps are randomly generated, or manually created (that can help in placing areas manually).
When you performance test an algorithm, don’t forget to let it run a few dozent times, that lets the VM do its optimization. (JIT compilation)
Often algorithms suddenly run faster after a while
This is the temporary map that I’m using (just trying to get all the basics down before spending more time on the design of the area), it’s 1600 x 1600 pixels. Basically the walls are closed/blocked nodes, as well as the rocks in the area. One of the problems I’m also having is that I want the game world to be 100x bigger, but I know if it’s any bigger it’s going to cause a lot of issues with entity paths as there would be a large number of nodes, it just wouldn’t scale well.
So I want to handle the game somewhat like RuneScape does, where you only update entities if you’re in the same region as them.
How would I approach this issue? One solution that I was thinking of is loading two separate maps. So basically the entire game map, which is all rendered at once (not sure how Libgdx handles very large regions, can anyone let me know?), and then a region map, which is the same as the game map, but broken down or spliced. So if a player is in a certain ‘region’, the pathfinding will only search for nodes in that area. But will still let you see the entire game world, so you don’t have to continuously see the black edges / the end of the game world. Not sure if that solution would work well, is there a better approach to this? I can already think of problems such as what if an entity is following the player, and then the player walks out to a different region.
Hi, oh there are many aproaches to your problem, I cant make a concrete example here, but throw in some ideas:
look at the solution starcraft had (also a tilebased map, having to cope with lots of path-calculations on 1997 hardware)
You see that they have separated the map into subregions wich are connected by a graph (the lines).
The units will first do a pathfind over this graph (the lines) to determine the regions to travel.
Once this is done, the units will use the local pathfinding (as you have it) to reach the next “centerpoint” of the next region the was calculated on the path.
So you basically do two pathfinds:
-1, along the graph connecting the regions
-2, locally for the region the actor is currently in, until entering a new region
so how to create those regions?:
-by code (using a floodfill algorythm that tries to MARK about the same amount of tiles for each region, the startingpoint are probably spawned accoring to a grid-pattern)
-by hand (tedious, but basically that means to make equally sized area-blobs, and assign each one another ID number; in your editor you could do that with another layer)
-then create that path-graph between those regions. Wich basically just means that any region touching another regions via at least one passable tile will have a connection between them (between its centerpoint, and the others centerpoint)
You can also use A* to search that graph, just google tutorials on A* that use non tile-based connection-graphs.
That would be the approach I try first if you want to use one huge continuous tile-map
Easier would be to have regions only connected by specific passages (North, South,East,West), and have those regions in the world aligned in a grid.
Then you can use your A* two times. Once between regions, and the second time within a regions.
(You have to be careful to assure that each passage can walk to the other 3 passages)
Tip: if you want to make a multiuser game: let the client calculate the path., then send that path to the server.
The server just checks if it does not violate any of your constrictions.
