So, I'm making a tactics style game where your character moves on a square-tiled map. When you click the character, the tiles on the map change to show which ones are within that character's move limit. This code works fine and the pathfinding code works fine, but there's one method that absolutely destroys the game for some reason. The process time goes from 16 to 500. Sometimes it even goes as high as 3000. This method is one where the tiles change once the character gets to the tile you told them to move to. This method updates all the tiles with the new distance to the player. I've already tried optimizing it once myself and it worked somewhat, but the more tiles it effects the worse it gets. So, right now I just can't give any character a move distance of more than 4 tiles.
Tips for optimization?
- Edited
One idea would be to just precalculate the distances betwen all of the tiles and keep them in memory before the game, but it won't be any good if the grid is super big and might require additional calculations if the way gets blocked
[I previously edited this out but got response to it so putting it back in so that the discussion is kinda readable:]
1do you need to keep distance information for all tiles? even the farthest ones?
2how do you calculate the distance in tiles? Every tile calculates for itself or in batches(like [player position+1][player position+2]
jamesantoni The distance is only stored in tiles that are within the player's range and they need the distance stored so that when you click on the tile the pathfinding can find a path equal to that number, to ensure that the quickest path is found. The way the distance is determined is by setting the tile the player is on to 0 and then setting all the tiles surrounding it to 1 and then all the ones surrounding those to 2 and so. Also, the distance is set within the tile atlas on the x axis.
So, I just change the tile to the next tile up in the tile set with set_cell(0, tile_set_1, 0, Vector2(x, 0))
BlueJellyCat the tiles change
In what way do the tiles change?
- Edited
BlueJellyCat I didn't fully understand how your system currently works and it's hard to give specific advice without seeing the code. I'm sure there's room for optimization on the algorithm level. But in general, if you need to do an intense on-demand calculation every so often - decouple it from frame update. Launch a worker thread and let the main thread do nothing for several frames (except regular visual updates) until results are delivered.
DaveTheCoder I use set_cell() to change the tile to one with a number on it, to show how many steps it takes to get to it.
xyz I don't know how to "decouple it from frame update" or "launch a worker thread," How would I go about that? Also, here's the latest version of the code I'm working with. This is after I already tried to optimize it myself.
- Edited
BlueJellyCat How do you know the code you posted is the bottleneck? Maybe the problem is in the caller, or somewhere entirely else. Hard to tell without seeing the whole thing. But I'm not sure doing stuff to the tilemap while you're performing the search is actually a good idea.
Launching a thread is simple:
var thread = Thread.new()
thread.start(self, "worker_function")Read up more on threads in Godot in the documentation. If you don't have any previous experience with concurrent programming, search for some online resources that explain the basic conecpts. They are the same in any programming language.
xyz The profiler points out this method specifically.
BlueJellyCat The profiler points out this method specifically.
Yeah but we don't see how many times or in what manner it's called.
- Edited
xyz It was called 3 times in this example. The CharacterBody emits a signal after it gets to the end of its path and TileMap2 receives it and calls the function. Also, when I turn this code off the process time doesn't go up anymore; It just stays around 16.
- Edited
- Best Answerset by BlueJellyCat
BlueJellyCat Firstly, you're calling get_cell_atlas_coords() twice as many times as needed. And secondly, you're needlessly iterating through a lot of already visited cells, since each call to get_surrounding_cells() will get you already handled cells too. You should probably use recursive flood fill algorithm for this, to minimize the total number of cell checks.
xyz So, I'm looking into flood fill now. Is there any reason why you suggested recursion instead of iteration? Is something about recursion better for what I'm doing?
- Edited
BlueJellyCat The algorithm is recursive in nature. You can implement it either way, although recursive implementation is a bit more elegant as it requires less code/data.