• Edited

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

    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 replied to this.
      • Edited

      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.

        • Edited

        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

        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 replied to this.
          • Edited

          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.

            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 replied to this.
              • Edited

              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.

              • Edited

              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

                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.

                xyz So, I messed around with what you suggested with your most recent code. I got it working very simply, where it would return a dictionary of all the top most cells, so then I sought to tweak it and make it return the top most cells as long as they didn't have a block directly on top of them.

                Example a tower of 4 blocks, that was every other cell would return a dictionary of 4 coords at the same xz. However, it would be accessed by the xz coords and then they would be sorted by another dictionary holding their elevations.

                Here is the code, it is quite rough, and I am sure not up to snuff.

                extends GridMap
                
                var map_cells: Dictionary
                
                func _ready() -> void:
                	map_cells = _get_top_cells()
                
                func _get_top_cells() -> Dictionary:
                	var top_cells: Dictionary
                	for cells in get_used_cells():
                		var cell_coords: = Vector2i(cells.x,cells.z)
                		if not top_cells.has(cell_coords):
                			top_cells[cell_coords] = []
                		top_cells[cell_coords].push_back(cells)
                	for x in top_cells.values():
                		x.sort_custom(func(a,b): return a.y > b.y)
                	return _get_moveable_cells(top_cells.values())
                
                func _get_moveable_cells(stack: Array) -> Dictionary:
                	var new_stack: Dictionary
                	for grp in stack:
                		var c: Vector3i = grp[0]
                		if grp.size() == 1:
                			new_stack[Vector2i(c.x,c.z)] = {c.y:c}
                			continue
                		if grp.size() == 2:
                			if abs(c.y - grp[1].y) >= 2:
                				new_stack[Vector2i(c.x,c.z)] = {c.y:c,grp[1].y:grp[1]}
                				continue
                			new_stack[Vector2i(c.x,c.z)] = {c.y:c}
                			continue
                		if grp.size() > 2:
                			new_stack[Vector2i(c.x,c.z)] = _sort_elevation(grp)
                	return new_stack
                
                func _sort_elevation(grp: Array) -> Dictionary:
                	var sorted: Dictionary
                	var under: bool
                	for c in grp:
                		if grp.find(c) + 1 == grp.size():
                			return sorted
                		if abs(c.y - grp[grp.find(c) + 1].y) > 1:
                			if under:
                				under = false
                				sorted[grp[grp.find(c) + 1].y] = grp[grp.find(c) + 1]
                				continue
                			sorted.merge({c.y:c,grp[grp.find(c) + 1].y:grp[grp.find(c) + 1]})
                			print(sorted)
                			continue
                		if sorted.get(c.y + 1):
                			continue
                		sorted[c.y] = c
                		under = true
                	return sorted

                I am also going to do some research on how to better search/compare elements in an array, maybe I should more of pop elements out of a stack or something of the sort to search elements.

                Edit: I wonder if I could do something like this with slice as well? It isn't finished but I need to go to bed.

                func _sort_elevation(grp: Array) -> Dictionary:
                	var sorted_dict: Dictionary
                	var sorted: Array
                	var first:bool = true
                	for x in grp.size() - 1:
                		var slice = grp.slice(0,2)
                		if first:
                			if abs(slice.front().y - slice.back().y) > 1:
                				sorted.append(slice.back())
                			sorted.append(grp.pop_front())
                			first = false
                			continue
                		if abs(slice.front().y - slice.back().y) > 1:
                			sorted.append(slice.back())
                		grp.pop_front()
                	return {}
                • xyz replied to this.
                  • Edited

                  xRegnarokx Again, way too much code. You could have just used my function that gets stacks. Since stacks are sorted by y, simply check if two last y coords in a stack are not adjacent or there's only one cell in a stack. If either is the case, you have a top cell with nothing underneath it:

                  func _get_floating_top_cells() -> Array:
                  	var stacks = _get_stacks().values()
                  	stacks = stacks.filter( func(s): return s.size() == 1 or abs(s[-1].y - s[-2].y) > 1 )
                  	return stacks.map( func(s): return s[-1] )
                  • Edited

                  xRegnarokx Oh, just realized you wanted all occupied cells that have space above them. Well that's even simpler. Iterate through all used cells and just check if the cell above is occupied:

                  func _get_platform_cells() -> Array:
                  	var platform_cells = []
                  	for c in get_used_cells():
                  		if get_cell_item(Vector3i(c.x, c.y + 1, c.z)) == -1:
                  			platform_cells.push_back(c)
                  	return platform_cells

                  Those could also easily be grouped in a dictionary with xz as a key. It's 2 additional lines of code.

                  EDIT: Why do all of this though? In a 2.5D game like this there should be no holes in stacks. So simply throw an exception if a hole is found. And display a message that the map is not designed according to rules 🙂

                    xyz Ahh that is right, you could just check if the cell above returns -1 and this is empty... duh...

                    Well as far as why to do this, in my game eventually I want to have bridges and such or platforms that are above that you can walk under (like there are in Tibia). In 2D there are no actual gaps it's just rendering order.

                    However, for 3D in 2.5D I assumed this was the best way to do that.

                    • xyz replied to this.
                      • Edited

                      xRegnarokx You're again trying to make a complex system before you made a simple system.

                      • Edited

                      xRegnarokx Here's a version of demo that can have holes. All tiles are now same sized cubes. It can handle any number of "bridges" one on top of another.
                      This is 15 additional lines of code compared to previous version. 60 lines in total in the whole project.

                      grid-movement2.zip
                      8kB

                        xyz Cool, thanks, I'll try and implement just that movement. Then I'll slowly add things to it such as other units moving, and detecting/setting occupation of tiles, ect... Thank you so much!

                        Edit: So, using your code I created a simple movement, and am working with it to understand it better. I did tweak it, and am planning on implementing obstacles to test it out, here is my occupied changing that I added.

                        func update_occupied(from: Vector2i,to: Vector2i,from_elevation: int, to_elevation: int) -> void:
                        	for cf in map_data[from]:
                        		if not cf.elevation == from_elevation:
                        			continue
                        		cf.occupied = false
                        	for ct in map_data[to]:
                        		if not ct.elevation == to_elevation:
                        			continue
                        		ct.occupied = true
                        • xyz replied to this.
                          • Edited

                          xRegnarokx Remember that the most important thing is figuring out the best fitting data structure(s) for the problem you want to solve. Doing so can simplify/shorten your code by the order of magnitude. Conversely, choosing inappropriate structure(s) can turn your code into a mess.

                          Time to yet again inject that timeless Fred Brooks piece of wisdom:

                          xRegnarokx Cool, thanks, I'll try and implement just that movement. Then I'll slowly add things to it such as other units moving, and detecting/setting occupation of tiles, ect... Thank you so much!

                          Note that adding other moving units to a system like this is trivial because movement only happens in respect to map data, and is instant. Only the visual representation shows (fake) gradual transition. So when you need to move the unit to some cell, just check if no other unit has its map position at that cell. If that's true, you can safely move it there.

                          xRegnarokx For completeness, here's the version with the player and arbitrary number of npcs, all moving and respecting cell occupancy of each other. As I already mentioned, this is trivial to add if you store your map/cell data in a proper structure.

                          We're now at 90 lines of code in total.
                          gridmap - 20 LOC
                          character base class - 50 LOC
                          player - 10 LOC
                          npc - 10 LOC

                          grid-movement3.zip
                          9kB