Moving in a grid, better method?

xyz · 7 Jan

xRegnarokx If it is 3D, I still am unsure if I understand how this would help me with finding the z index for movement purposes. How is my character if I am not using the build in physics to know where they should be on the z index.

There's literally z property in the cell data which holds the integer number of stacks. If you know the height of one stack, multiply z with that height and you've got the vertical position in the world. It's basically a simple version of heightfield.

If you compare z of the current cell and z of the cell you want to go to, you'll know if you need to climb, descend or go straight. Or if a cell is an obstacle that is not climbable etc.. All this can and should determine how you animate the traversal.

XxRegnarokx · 7 Jan

xyz Ahh okay, so you'd set the z based on its height then you'd be able to find it using Vector2i, which would just ignore the z index. I think I was confused since you had Vector2i, I wasn't thinking about the fact you could set up a grid like that, where the z index is stored separately to enable reliable cell discovery. I am still wrapping my mind around doing things in 3D and coming from 2D the z has been throwing me off.

Thank you so much! You have always pointed me in a good direction. I'll leave this open until I can create some test code to see if I am able to utilize these principles.

xyz · 8 Jan

xRegnarokx Note that z is perhaps a wrong name to use here. Height would be much more appropriate as it's not linked to any coordinate system. In Godot's 3d the convention is that a ground plane is in x and z directions and up is in y direction.

Here's a more elaborate "sketch" of how the whole map class could look like. Don't just copy paste this. Might not work. It's just to show the way of thinking/organizing.

class_name Map extends RefCounted

# cell data struct
class Cell:
	var terrain: String = "grass"
	var height: int = 0
	var walkable: bool = true
	func _init(iterrain: String, iheight: int, iwalakble: bool = true): # object constructor
		terrain = iterrain
		height = iheight
		walkable = iwalakble
	
# map size (number of cells)
var _size: Vector2i

# map
var _cells: Array[Cell]

# pyisical cell size
var _cell_size_physical: float = 1.0 # xz size of a cell in world units
var _cell_height_pyhsical: float = 1.0 # height of a cell in world units

# initialize the size of array that holds cell data
func initialize(size: Vector2i):
	_size = size
	_cells.resize(_size.x * _size.y)
	
# returns 1D array index from 2D cell coords, depending on map size 
# used to access a 1D array as if it was a 2D array
func _get_array_index(pos: Vector2i) -> int:
	assert(pos.x >= 0 and pos.x < _size.x and pos.y >= 0 and pos.y < _size.y) # boundary check
	return pos.x + pos.y * _size.y
	
func get_cell(pos: Vector2i) -> Cell:
	return _cells[_get_array_index(pos)]
	
func set_cell(pos: Vector2i, data: Cell) -> void:
	var cell = get_cell(pos)
	cell.terrain = data.terrain
	cell.height = data.height
	cell.walkable = data.walkable
	
# some test utility function
func add_wall(pos: Vector2i) -> void:
	set_cell(pos, Cell.new("wall", 1, false))
	
func add_barrel(pos: Vector2i) -> void:
	set_cell(pos, Cell.new("barral", 1, true))
	
# etc...

Now you can use some generation algorithm to generate an actual maze or map layout into this structure. And when you have that, you can proceed to make a visual representation of it in either 2d using fake ortho perspective or in 3d using actual geometry.

If you prefer visual editing of the map, You can make an actual GridMap with some tiles etc... and write an utility script that interprets what's in the GridMap and populates your data structure.

Alternatively you could implement the same data structure as an extension of a GridMap node, making it more coupled with actual 3D graphics, but the way of thinking about and organizing map data would be exactly the same. You need a "logical" structure that's "underneath" the visual representation.

The movement comes after this, because the movement system needs this for proper functioning. You can't really have a grid based movement system without some data in a grid

XxRegnarokx · 8 Jan

xyz Awesome, I appreciate the example. I try not to copy and paste, unless there is something I'm using as a template and am planning on rewriting anyway. I find writing the code myself helps me understand better what is going on.

This makes sense, so, if I do the visual design -> data structure I will create a system to translate the visual fluff to actual useable information in the map data.

So, since I want to go visual design -> map data route, I also need to think through how I am going to translate the gridmap visuals into the cell/map data.

XxRegnarokx · 8 Jan

xyz Could I use metadata for setting certain data of my cells? Such as setting metadata of base height of a tile. Or unpassable, or a myriad of different things that could then be grabbed while creating the cell classes. Would this work, or is this a bad idea/practice?

xyz · 9 Jan

xRegnarokx Technically you could store all cell data into metadata of the gridmap meshes. In that case you wouldn't need a custom Cell class or an array of cells, although the code that access the cell data would be a bit more verbose.

XxRegnarokx · 9 Jan

xyz Yeah, I realized that as I was running into that issue when I was looking at how that would work.

Also, I noticed you used assert() inside of _get_array_index(). What is this used for (boundry checks obviously)? Just reading its description it sounds like it only used for debugging purposes, and doesn't do anything when exported? Or am I not understanding its description in the documentation?

Also, I noticed in the assertion that you were checking that there wasn't negative value x and y coords? Would you then recommend that when I am setting up my cells that I keep them increasing from 0,0? So, my absolute top left cell would be 0,0 and then I would go from there?

xyz · 9 Jan

xRegnarokx assert() there is just a hint that boundary check should be implemented here. You can do it in any way that fits your system.

Cell coordinates can be in any range although starting at 0,0 may make code simpler. Again, this is implementation detail that depends on characteristics of your system. The decision on how exactly to do it is yours to make.

xyz · 9 Jan

xRegnarokx The important thing to understand here is how this will facilitate movement handling.

In a grid based system, a character/entity can occupy only one cell, and it must occupy exactly one cell at any given time. There's no transitional state in such a system. All movement happens instantly. When a character is moved, it immediately should hop from one cell to another. Smooth animation of movement from cell to cell is just a visual effect that happens after the underlying state has already been changed.

Knowing this you should first implement the instant movement. When a command is pressed, check if the movement from the current tile to the next tile is possible (by looking at the cell data and applying movement rules). If yes - change the underlying state and update the visual representation to reflect that state.

Upgrading the system to smooth transitional animations is then just a matter of interpolation/animation and preventing further movement until the current animation is finalized.

XxRegnarokx · 9 Jan

xyz Hey, thanks for that! Also, that makes sense with assert, I'll work on making a boundry checker to my current code. I feel like maybe I'm going over complicated with what I am doing, maybe I'm missing something. I have still some bugs I'm ironing out, here is what I have so far, it is more to try and judge if there are any critical flaws in my thinking as I am implementing this data structure and converting the visual to be translated into the data structure.

extends GridMap

class Cell:
	var height: int
	var walkable: bool
	func _init(iheight: int, iwalkable: int) -> void:
		height = iheight
		walkable = iwalkable

# map size (cell number)
var _size: Vector2i

# map (array of cells)
var _cells: Array[Cell]

# cell size in world units (meter)
var _cell_size_physical: int = 1
var _cell_height_physical: int = 1

# sets up array size holding cells
func initialize(size: Vector2i) -> void:
	_size = size
	_cells.resize(_size.x * _size.y)

func _get_array_index(pos: Vector2i) -> int:
	assert(pos.x >= 0 and pos.x <= _size.x and pos.y >= 0 and pos.y <= _size.y)
	return pos.x + pos.y * _size.y

func get_cell(pos: Vector2i) -> Cell:
	return _cells[_get_array_index(pos)]

func get_cell_pos(pos: Vector2i) -> int:
	return _get_array_index(pos)

func set_cell(pos: Vector2i,data: Cell) -> void:
	print(get_cell_pos(pos), data)
	_cells[get_cell_pos(pos)] = data
	#var cell = _cells.insert(get_cell(pos),data)
	#cell.height = data.height
	#cell.walkable = data.walkable

# list of all tiles
var used_cells: Array[Vector3i]
# saves the tile type of each tile in used
var cell_item: Array
# translates the used_cells coords to Vector2i
var cell_coords: Array[Vector2i]

func _ready() -> void:
	used_cells = get_used_cells()
	for cell in used_cells:
		cell_item.append(get_cell_item(cell))
	for pos in used_cells:
		cell_coords.append(Vector2i(pos.x,pos.z))
	cell_coords.sort_custom(_sort_descending)
	initialize(_get_size(cell_coords[0],cell_coords[cell_coords.size() - 1]))
	setup_cell_grid()

func setup_cell_grid() -> void:
	cell_coords.sort_custom(func(a,b): return a.x + a.y < b.x + b.y)
#	var count : int
	var grid_count: = Vector2i(0,0)
	for cell in cell_coords:
		for used in used_cells:
			if cell == Vector2i(used.x,used.z):
				set_cell(grid_count,Cell.new(0,true))
				if grid_count.x < _size.x:
					grid_count.x += 1
				elif grid_count.y < _size.y:
					grid_count.x = 0
					grid_count.y += 1
				else:
					print("what happened?")
#				count += 1
#				print(count)

func _sort_descending(a,b) -> bool:
	if a.x + a.y > b.x + b.y:
		return true
	return false

func _get_size(num1: Vector2i, num2: Vector2i) -> Vector2i:
	var val_x: int
	var val_y: int
	if num1.x <= 0:
		val_x = abs(num2.x) + num1.x + 1 
	elif num2.x < 0:
		val_x = abs(num2.x) + num1.x + 1
	else:
		val_x = num1.x - num2.x + 1
	if num1.y <= 0:
		val_y = abs(num2.y) + num1.y + 1 
	elif num2.y < 0:
		val_y = abs(num2.y) + num1.y + 1
	else:
		val_y = num1.y - num2.y + 1
	return Vector2i(val_x,val_y)

xyz · 10 Jan

xRegnarokx If you plan to use gridmap's cells then best to store your cell data in a dictionary with keys being Vector2i coords of the cell, instead it being an array. Using an array presupposes that all cells in a rectangle of cells defined by _size are populated, however with grid map there's no such constraint.

And yeah, you did verbatim copypaste my code. Don't do that. It likely won't work, especially not as an extension of a GridMap node. Write everything from scratch.

So if you want to play nice with gridmap in a simple way - maintain a dictionary of cell data objects with key being a Vector2i or Vector3i that represents cells' 2d or 3d coordinate. This will effectively extend gridmap's cells with your custom data.

extends GridMap

class CellData:
	# cell data here

var _map_data: Dictionary

func _ready():
	for cell_coord in get_used_cells():
		var cell_data = CellData.new()
		match get_cell_item(cell_coord):
			0:
				# popualte cell_data depending on item	
			1:
				# popualte cell_data depending on item	
			# etc..
		_map_data[cell_coord] = cell_data

XxRegnarokx · 10 Jan

xyz Awesome thanks.

I tweaked the code that actually populated the cells from what you wrote, I mainly used the logic of set, get, and it was useful to see how you used the get_index to get a 2d position in a 1d array.

But you are right that for what I am trying to do it won't work. Since how I have it set up will only work for rectangular maps.

I will start from scratch with what I've learned from your previous suggestion, and your new one suggesting placing the cells in a dictionary with Vector2i/3i as key.

I'll have to think through which would be better.

Having Vector2i as keys I would have to write a way to have the height of the cell overwrite other lower entries if they are stacked on top otherwise it wouldn't include the top cell.

Or to have a dictionary of dictionaries, where the first key is height, then the cells of that height are placed in a dictionary.

Or just place an array of cells under keys that have multiple cells at the Vector2i coord.

Or calculate all of that and discard any cells that aren't walkable because a cell is on top of it.

I'll think through these problems and see what I can do to implement a gridmap based data structure.

It may be more streamlined to use the Vector3i coords.

xyz · 10 Jan

xRegnarokx Think about whether you really need stacking of 3d cells. Imo this could better be handled by using only a single floor of gridmap with different cell elevations. You don't need an actual 3d grid.

xyz · 10 Jan

xRegnarokx Here's a demo:

You can toggle between smooth and instant movement via flag in the character node. It's 60 lines of code total. Dummy rules of movement are that cells can be traversed if the elevation difference is 1 or 0.

grid-movement.zip

9kB

XxRegnarokx · 10 Jan

xyz Thanks so much for that demo! That looks a lot like what I'd like to eventually accomplish.

Question about the single floor with different cell elevations. Do you mean having blocks that are 1,1,1 and 1,2,1? So rather than stacking a block of height 1 to create an elevation difference you'd just use a block that has a height of 2?

Or are you thinking this would be implemented in another way?

I just don't know how that would look if you have a map with large elevation changes. Or would you just create another gridmap for the new elevation?

Or are you talking more on the data implementation side? To not worry about storing info for stacked cells, but just store the top most cell with a height value? That way you could use Vector2i coords and then just check height?

xyz · 10 Jan

xRegnarokx Question about the single floor with different cell elevations. Do you mean having blocks that are 1,1,1 and 1,2,1? So rather than stacking a block of height 1 to create an elevation difference you'd just use a block that has a height of 2?

You can do it in various ways depending on the actual content and rules in your game, but it's all similar in respect to elevation data storage. You always only need the topmost elevation (if stuff is always stacked). Whether you stack all inside a single mesh or use several gridmap floors, makes no difference really. I used what you described here as it it requires the least code and the simplest setup.

Study that demo. It should clarify things a bit.

XxRegnarokx · 11 Jan

xyz So, here is what I've wrote, I tried to make it before then looking at your demo code so, I wouldn't be tempted to imitate it first. I noticed that your code seemed like it would just grab the top tile, regardless if there was a tile directly under it. So, what I tried to do was write something that would sort the top tiles, and also find if there were any tiles that were underneath with a gap between them.

I am still trying to make it fully accurate, it will get me the tiles that I want, but also there are certain cases where another tiles slips by that isn't actually not in the stack.

I'll keep working on it tomorrow, but thought I'd post it here.

extends GridMap

class CellData:
	var height: int
	var has_below: bool
	var is_below: CellData
	func _init(iheight: int, ihas_below: bool, iis_below: CellData) -> void:
		height = iheight
		has_below = ihas_below
		is_below = iis_below

var map_cells: Dictionary

func _ready() -> void:
	_get_map_cells()

func _get_map_cells() -> void:
	var sort_cells: Array[Array] = _sort_cells()
	for primary in sort_cells[0]:
		var add: = Vector2i(primary.x,primary.z)
		for secondary in sort_cells[1]:
			if not primary.x == secondary.x:
				continue
			if not primary.z == secondary.z:
				continue
			map_cells[add] = CellData.new(primary.y,true,CellData.new(secondary.y,false,null))
		if not map_cells.get(add):
			map_cells[add] = CellData.new(primary.y,false,null)
	for cell in map_cells:
		if map_cells[cell].has_below:
			print(map_cells[cell].is_below.height,map_cells[cell].height)

func _sort_cells() -> Array[Array]:
	var used_cells = get_used_cells()
	var sorted: Array[Vector3i]
	var below: Array[Vector3i]
	#finds the top tiles of the gridmap, and potential tiles below others
	for first_cell in used_cells:
		var cell_test: Vector3i = first_cell
		for second_cell in used_cells:
			if first_cell == second_cell:
				continue
			if not first_cell.x == second_cell.x:
				continue
			if not first_cell.z == second_cell.z:
				continue
			if not first_cell.y < second_cell.y:
				continue
			if abs(first_cell.y - second_cell.y) > 1:
				if not below.has(first_cell):
					below.append(first_cell)
			cell_test = second_cell
		if not sorted.has(cell_test):
			sorted.append(cell_test)
	#finds only the cells in the below array that is below another tile, and not stacked
	for cell2 in below:
		var cell_below: = Vector3i.ZERO
		for cell1 in sorted:
			if not cell1.x == cell2.x:
				continue
			if not cell1.z == cell2.z:
				continue
			if not abs(cell1.y - cell2.y) > 1:
				continue
			cell_below = cell2
		if cell_below:
			below.pop_at(below.find(cell_below))
	print(sorted,below)
	return [sorted,below]

xyz · 11 Jan

xRegnarokx No, I just used a single floor gridmap with hardcoded elevation.
Make the simplest version first. Then upgrade and add finesse and complexity.

In general, your code looks too complicated. It's also too deeply nested.

Take a look at the demo to see how simple this actually can be. I just updated it with even simpler version, so download it again if you already did so previously. It's 15 lines of gridmap code and 35 lines of character code. That's all.

xyz · 11 Jan

xRegnarokx Oh, and if you want to get all top cells, it can also be done in a much simpler way. Simply iterate through all used cells and maintain a dictionary whose key is xz cell coordinate. Whenever you encounter the same xz coordinate, compare its y with the y in the dictionary and overwrite the value if the y is larger than what's already stored. At the end of iteration your dictionary values will be top cells:

func _get_top_cells() -> Array:
	var top_cells: Dictionary
	for c in get_used_cells():
		var c_xz = Vector2i(c.x, c.z)
		if not top_cells.has(c_xz) or c.y > top_cells[c_xz].y:
			top_cells[c_xz] = c
	return top_cells.values()

This can also be easily extended to find whole stacks. Just store all cells with same xz in an array under the xz key and in the end sort each of those arrays by y:

func _get_stacks() -> Dictionary:
	var stacks: Dictionary
	for c in get_used_cells():
		var c_xz = Vector2i(c.x, c.z)
		if not stacks.has(c_xz):
			stacks[c_xz] = []
		stacks[c_xz].push_back(c)
	for s in stacks.values():
		s.sort_custom(func(a, b): return a.y < b.y)
	return stacks

XxRegnarokx · 11 Jan

xyz Okay, I'll redownload the demo. Also, I'll work on implementing a more basic system, and as I develop and run into needs will tweak it.