Hello, I am a complete noob to godot and am playing around to learn some fundamentals. I have a question how to go about grid based games. For example conways game of life or a Qix style game.
Would the correct way be to use a TileMapLayer to draw on? I noticed that working directly with the tilemap in the calculations is quite slow. So is a better approach to use arrays to do all the calculations and then update the tiles in the last step? Or would it be better to use a canvas and draw on that? How would one make a well performing game of life?
Welcome to Godot! If you’re planning to draw manually on the canvas during runtime, TileMap really isn’t the best choice because it’s mainly intended for placing premade, static graphics in a predefined grid and isn’t optimized for frequent updates or dynamic visuals (except animated tiles of course). For grid-based games like Conway’s Game of Life or Qix-style mechanics, a better approach is to use a 2D array (Array2D, or PackedByteArray if you’re optimizing for memory and performance), handle all the logic and state updates in the array, and then draw the result manually on the canvas each frame.
Thanks mrdicerack.
It seems that the drawing is not the bottleneck. My update of the grid of 100*75 cells only takes about 2ms. The flood fill calculation on the other hand takes almost 300ms. That seems much to long for such a limited amount of cells. I implemented the 2d array with
grid.resize(width)
for i in range(width):
grid[i] = Array()
grid[i].resize(height)
for j in range(height):
grid[i][j] = 0
I could not seem to use Array2D as a type. So I will have to check what is going on with my flood fill.
You’re welcome! For maximum optimization, try experimenting with using ImageTextures and Images. I believe you can do ImageTextures in code. They are faster to render than drawing manually on the canvas.
Also, I called it Array2D, but it’s just a 2-dimensional array, sort of like a Vector2D.
You can make a multidimensional array out of a one dimensional array trivially:
const GRID_X: int = 1024
const GRID_Y: int = 1024
const GRID_CELLS: int = GRID_X * GRID_Y
var Grid: Array = [].resize(GRID_SIZE)
# Write to a cell.
func write_cell(pos: Vector2i, val: Variant) -> void:
Grid[pos.x + (pos.y * GRID_X)] = val
# Read the contents of a cell.
func read_cell(pos: Vector2i) -> Variant:
return Grid[pos.x + (pos.y * GRID_X)]
# Iterate over the grid.
# This function expects a Callable of the form:
# func foo(pos: Vector2, val: Variant) -> void
func iterate_cells(fn: Callable) -> void:
for i: int in GRID_CELLS:
var pos: Vector2i = Vector2i(i % GRID_X, i / GRID_X)
fn.call(pos, Grid[i])
The x + (grid_size_x * y) scheme works in pretty much any language. You can extend the logic to higher dimensions as well; x + (grid_width_x * y) + (grid_size_x * grid_size_y * z)…
Hello hexgrid,
thanks for the reply. I tested your suggestion and made a simple benchmark with setting 1024*1024 cells with each approach. Seems yours is somewhat faster. Although implementing it into my flood fill test program it did not make any noticeable difference. The execution of the entire calculation still takes just under 300ms. So I guess the problem must lie somewhere else. Could it be that “if value in array:” is very time consuming?
Anything that happens in gdscript is going to be relatively expensive compared to compiled code. Computers are pretty fast these days, though, and 7500 cells isn’t too many.
What kind of behavior are you trying to give these cells?
The code I wrote above was for illustrative purposes, so things are cleanly separated by purpose, but if you want things to go fast, there are lots of opportunities for optimization. If I were doing something like this, I’d probably make things power of two sizes so I could use bit manipulation to speed things up. I would also directly operate on cells rather than mapping; function invocation isn’t too expensive, but when you’re doing it for every cell in a grid it adds up.
const GRID_X: int = 128
const GRID_X_MASK: int = GRID_X - 1 # Only works if GRID_X is a power of 2...
const GRID_X_SHIFT: int = 7 # 2^7 == 128
const GRID_Y: int = 64
const GRID_CELLS: int = GRID_X * GRID_Y
func do_cell_stuff() -> void:
for i: int in GRID_CELLS:
var pos: Vector2i = Vector2i(i & GRID_X_MASK, i >> GRID_X_SHIFT)
# Do whatever inline here.
# Surrounding 8 cells are:
# +------------------+------------+------------------+
# | i - (GRID_X + 1) | i - GRID_X | i - (GRID_X - 1) |
# +------------------+------------+------------------+
# | i - 1 | | i + 1 |
# +------------------+------------+------------------+
# | i + (GRID_X + 1) | i + GRID_X | i + (GRID_X - 1) |
# +------------------+------------+------------------+
If you want to make things quicker, make the grid slightly bigger than you need and put a border of empty cells around it so you don’t have to check if you’re stepping off the grid. You could also do this as a nested loop:
func do_cell_stuff() -> void:
var index: int = 0;
for y: int in GRID_Y:
for x: int in GRID_X:
[...stuff...]
index += 1
The way that code walks the array, index will always be the correct value for that x, y in the grid.
Hello,
so basically I am playing around with a Qix like game fill algorithm. Its my first attempt to learn a few things in Godot. I have attached my flood fill function. I got the basic idea from some example and modified it. It only fills one side for testing without any fancy stuff. width is 100 an height is 75. Yet this function alone takes near 300ms. My PC is new and quite fast, so that should not be the cause. Maybe it would be better to implement this function in C++?
func ffill(start) -> void:
var time_start = Time.get_ticks_usec()
const DIRECTIONS = [Vector2i.LEFT, Vector2i.RIGHT, Vector2i.UP, Vector2i.DOWN]
var fill = []
var stack = [start]
var index : int = 0
var cm : int = 0
var cn : int = 0
while stack.size() > 0:
cm += 1
var current = stack.pop_back()
if current in fill:
continue
if grid[current.x+(current.y*width)] == grid_empty:
fill.append(current)
for dir in DIRECTIONS:
cn += 1
var neighbor : Vector2i = current + dir
if neighbor in fill:
continue
if grid[neighbor.x+(neighbor.y*width)] != grid_empty:
continue
if not neighbor in stack:
stack.append(neighbor)
if current == start:
break
for cell in fill:
grid[cell.x+(cell.y*width)] = grid_done
time_start = Time.get_ticks_usec() - time_start
print("cm " + str(cm))
print("cn " + str(cn))
print("C " + str(time_start))
Flood-fill is a nightmare. Doing it the simplest way, which it looks like you have, is the most expensive way and longest. When I tried making my own, I wound up getting a stack overflow due to bad implementation.
Eventually I went with a kind of algorithm I no longer remember the name of, but one of the sites I had used was this:
I’m still wondering how MSPaint manages to fill nearly instantly, yet when I have a similar thing for a simple image+click, mine is slower… although another commenter pointed out the code from running a test in the editor may be much slower than when the game is compiled, which would explain a lot.
Aand I did a quick test and it looks like there’s 20~60 milliseconds gain in speed when using my flood fill on an exported project vs. testing the scene/project from Godot.
This seems like a kind of an expensive way to do a floodfill. Typically, either you want to do a floodfill instantly or iteratively.
If you want instantly, starting position and order don’t matter, so you can just do this as:
func instant_flood_fill(x: int, y: int) -> void:
for i in x * y:
grid[i] = grid_done
If you want to do iteratively so the player can watch it fill, rather than a stack I’d use an identical grid; iterate over the new grid setting anything that’s set in the old grid, and anything whose neighbor is set in the old grid. One call of the function expands the flood fill by one cell in all directions. Repeat as needed; since you’re doing an iterative scan you can keep a count of unset cells, and when that hits zero you’re done.
Using a grid to hold the metadata isn’t going to take much more space than a stack (and it may take less), and there’s no stack management or recursion to deal with.