Moving in a grid, better method?

XxRegnarokx · 5 Jan

So, I have a method of moving in a grid, I can post tomorrow if people want to see. However, I recently switched to making my 2D game in 3D, and 3D is infinitely more difficult then 2D. At least when you don't want just free movement aided by physics engine.

Currently I use move_and_slide along with raycast to move my character around, while snapping and having a timed system to prevent the character from moving more than the desired grid distance. This has many flows and creates potential nightmares once there are multiple bodies moving around.

So, is there an easier or at least more intuitive way to implement grid movement in 3d? I thought about implementing a basic navigation system, where all tiles on the gridmap are stored as keys in a dictionary and their class cell is stored which holds an array of up to 4 moveable directions around them.

I guess 3D is a lot harder for me to implement clean movement code in a grid. Tempted to abandon grid movement, but that changes my game feel/design a lot.

xyz · 5 Jan

xRegnarokx If this is turn based, you don't need any character bodies. Disable collisions and chain the move sequence into a tween.

XxRegnarokx · 6 Jan

xyz It isn't turn-based unfortunately or that'd be easier. It is a 2D style gridbased rpg made in 3D because of the perspective.

xyz · 6 Jan

xRegnarokx What does "gridbased" mean then? Perhaps describe how exactly should your movement mechanics look from player's perspective.

XxRegnarokx · 6 Jan

xyz From a players perspective you move smoothly as long as you are pressing movement inputs. However, whenever you release the character will end up at a vector3 where the x and y coords are in 1 meter whole increments. So, by gridbased I mean the player is locked to a 1x1 grid horizontally, they'll never stop on a none whole number.

xyz · 6 Jan

xRegnarokx So there is no movement path? The character just moves one of the 4 or 8 direction as long as the command is held pressed? And it can only stop exactly at a grid unit, not inbetween grid units?

XxRegnarokx · 6 Jan

xyz Yes, currently there is no movement path. The player currently has a shape cast that they cast .9 meters in the direction they want to move. Currently after each move_and_slide the player is snapped to a float value position that goes into 1 evenly that is created based on the players speed. So, the move_and_slide moves the character a set amount each frame, and there is a timer that equals 1/speed float value.

So.

If nothing is .9 in direction of movement, move.

If moving set timer to equal 1/speed float value.
Each frame reduce timer by 1
Move_and_slide
Snap vector3 to value of 1/speed float value.
Once timer = 0 reset movement
And snap to vector3 with a value of 1

xyz · 6 Jan

xRegnarokx A bit too complicated for a mere grid movement but it can work. Where's the actual problem?

XxRegnarokx · 6 Jan

xyz I guess the "a bit too complicated for a mere grid movement" haha. Once I have multiple entities moving around I am worried it will create larger problems with how complicated it is, also shapecasting for moving to a location is unreliable if two objects want to move into the same area at the same time they won't detect collisions until they do, that will force them to either overlap, or stop not in a grid_position. So, if I make the raycasts longer to detect the "next" move increment, that doesn't account for coming from another angle into the same space...

I am just running into a bottleneck on how to implement a movement that locks everything to a x,y of 1 meter, while allowing for the z index to be handled by physics, rather than manually changing it as well (though that may be what I have to do). If I don't use move_and_slide is there a reliable way that I can get the z index of the terrain, so that I can maybe interpolate the position, ignoring physics interactions and setting up an occupied tile array for positions? I guess the moment the z index comes into the picture in a game that I am trying to emulate psuedo 2D it makes it complicated for me to navigate movement.

I considered setting up like an Astar movement alongside a gridmap and using that as a base, with the array that stores occupied tiles, however, I am running into how to implement an Astar in 3D, I've implemented it in 2D several times, along with my own very basic custom movement algorithms. I am struggling how to get the Vector3, and if I get them is it the top of the object or the middle, or bottom...

xyz · 7 Jan

xRegnarokx You're overcomplicating this on several levels.
First, if your movement is grid based, then you need a custom data structure that holds the grid data, including occupancy info. I think I already suggested that. Doing shapecasts (i.e. physical collisions) is antithetic to grid organization. The whole purpose of having a grid system is to not need to do map collisions. A grid cell can either be occupied or not. It's a logical state, not a matter of colliders it the scene. Once you establish such structure, it'll be much easier to handle movement. Some impassable areas may not even be detected by collisions (e.g. bodies of water). So implement a logical cell occupancy data structure first.

Next, implement "instant" movement from cell to cell, that checks for occupancy in the occupancy map and handles the positioning onto cell coordinates properly.

Next, interpolate that instant movement using tweens or manual lerping in _process().

When you have this in place, we can talk about how to handle unit overlaps. It can be done with the above system without any complicated additions.

XxRegnarokx · 7 Jan

xyz I guess the part that is the part I'm struggling to consider is creating the occupancy data structure. You recommended A* which I am familiar with in 2D. My confusion is setting up the grid structure, implementing lerp/tween.

Using A* can I eventually have more data stored in points for different movement type, water, rough terrain, ect... or do I need to build a custom grid data structure storing other information? If that is the case would it be sufficient to use a a* to create all the points then run the points through a custom structure adding the additional information? Or should I just start and build my own data structure.

The biggest barrier I have is how to I get the point coordinance for the cells that == the top of each cell?

xyz · 7 Jan

xRegnarokx I don't think I recommended A* in your latest batch of questions. A* has nothing to do with movement per se. It's a path finding algorithm. For simple cell to cell movement you don't need any such fancy stuff. You just need a 2D array the size of your gird, populated with boolean values that signify if a cell is occupied or not. That's all there is to a basic occupancy structure. Later you can upgrade it so that each cell holds a terrain type or whatever other cell info. But for basic occupancy, you just need to store one bit of information per cell.

XxRegnarokx · 7 Jan

xyz Okay, I don't know if I'm communicating my barrier. How do I get the Vector3 for moving to a cell? With the Z index I'm not sure how to handle that.

xyz · 7 Jan

xRegnarokx Your barrier is that you've set up your system too complicated and painted yourself in the corner with it. I'm telling you to re-do your system so that doesn't happen.

You also ask specific questions without describing your setup precisely. How do you get Vector3 for moving to a cell from where? Is the map flat? Is it a heightfield? Are you using GridMap? Etc.

In general you need to implement a function that calculates a world position from a grid position and vice versa. Similar to tilemap's map_to_local() and local_to_map(). For that you need to know your grid unit size and your grid origin. Calculation then simply boils down to translating the input position so that both spaces's origns match and multiplying/dividing it with cell size. If your grid and your world origin coincide, then you only need to multiply/divide with the cell size.

XxRegnarokx · 7 Jan

xyz Sorry for not sufficiently describing my setup. The reason is because I am trying to visualize how to move forward without what I have for movement because like you said it is very complicated. Currently I move without calculating a specific coordinate, but just moving by 1 meter increments. However, if I want to implement an occupancy data structure that will not work well, and also, for using tween or lerp that doesn't work, it requires physics to keep z on the grid.

So, I have no setup yet because I am trying to figure out how to move forward. The problem is figuring out how to get the Vector3 before I can move forward with a more pure grid movement. So, how do I create a data structure of cells that have the Vector3 of the cells that I can use for finding the information of the cells, as well as moving via lerp or tweens.

I think I can figure out x,y locations to create a calculation between world coords and local. However, if I use gridmap for example, if I have tiles that have different heights how do I figure out their z index coord. Or do I just need to standardize all the heights and put them in different layers/gridmaps that each have their own z index height?

xyz · 7 Jan

xRegnarokx What is z index you're referring to? In 3d, you don't need any z index. You can simply have continuous elevations.

You should first describe your map. How is each cell defined via its logical properties (terrain, elevation etc) and then how you plan to represent that visually. Then we can discuss how to reflect that in your custom grid structure and how it can all be turned into movement in 3d space.

Or better yet, give a reference to an existing game that's similar to what you're trying to do.

XxRegnarokx · 7 Jan

xyz Okay, I guess I am not understanding what you mean by continuous elevations. If you have a cell at z index 0 and one at 2 how would you handle if you wanted jump off the ledge to get to the 0 tile, or if you have stair tiles that halfway up would be at z index 1.

I guess I am inspired a bit by an mmorpg called Tibia, at least it gave me the idea for the perspective. I believe is is 2D but with a perspective that gives it more depth. Also, in it you can climb on stacked objects to climb onto ledges.

xyz · 7 Jan

xRegnarokx Oh so there's vertical movement as well? You should have mentioned that from the start. Best to post some gameplay/movement footage.

I googled Tibia gameplay videos. All movement there appears to be happening on the floor plane.

XxRegnarokx · 7 Jan

xyz Yeah, it is since it is 2D there isn't an actual z axis in tibia, they simulate it though where items can get stacked, and players can climb onto stacked items.

Here in the first few seconds you see someone standing on a barrel in the bottom left in the building. I know in 2D this is smoke and mirrors, but I wasn't able to figure out the perspective challenges in godots 2D engine. The sorting characters behind objects both on the x and y axis.
[

So, I want to try and emulate that in 3d, but that is granted more difficult. But, I am confident I can figure out what I need if I can find a way to get the z index of the top of terrain. Objects are easy, but the tiles on the gridmap are harder.

xyz · 7 Jan

xRegnarokx You should start by modeling your map with data. Introduce a cell class that contains relevant cell data

class Cell:
	var z: int = 0 # how many stacks, your "z index"
	var walkable: bool = true
	# add more stuff later

Have a "2D" array of such cells that represents your map:

var map: Array[Cell]

The array is 1D (since there are no multidimensional arrays in GDScript) but you can implement 2d access functions so it'll work like a 2D array/map:

func get_map_cell(map_coord: Vector2i) -> Cell:
	# stuff

func set_map_cell(map_coord: Vector2i, cell: Cell) -> void:
	# stuff

That's your basic map data structure. You can do a lot with it.