Plotting complicated gridbased movement

xRegnarokx

So, I was thinking in order to make it simpler for the player, I would change my movement design.

What I need: A system the highlights all movable tiles in a hexgrid. Movable tiles are those tiles which the ship can move to within their move_speed(changes throughout game). Also, it needs to take into consideration the ships rotation_cd(which indicates how many tiles the ship needs to move before being able to rotate again). This is so the player can visualize all spaces the ship can move without having to imagine it in their head while only being given highlighted tiles in their ships pointed direction.

So, I have a fully functioning movement system that does what I want game mechanic wise, but not as intuative as above. I have a system that plots tiles the ship can move to in a straight line, based on move_speed, I can also rotate ship and set it into cd that will not allow me to rotate before I've moved the given tiles.

However, this doesn't seem intuitive for the average person. I am happy with it, but am wondering if there are any suggestions on what direction to head to preplot out all possible movement. I can manually do it via code by doing the calculations and inputting everything by hand, however that isn't good, and doesn't allow for changing variables.

Does what I want to do make sense, and if so is it reasonably possible in code?

xyz

xRegnarokx Sounds complicated as a mechanic. Maybe try to keep as simple as possible for the player.

xRegnarokx

xyz Yeah, that is why I'm trying to show movement by highlighting the tiles for the player. What I currently have is fine for me, but I realize I'm a nerd that likes complicated things that force me to think.

That is why I am trying to figure out how to just visualize all potential movement for the player. It is more complicated for me, but simple for the player, they'll see where they can move and can choose.

The problem is due to turn cd I am unsure how to calculate that. Yes, I could just scrap increasable/decreasable speed and turn cd. Then I'd just make a tactics game like all the rest. A large portion of strategic positioning would be removed if I did that. Also many of the advantages of smaller more agile ships would be removed.

I am trying to make it a simple point and click for the player. However, I don't know if that is feasible with what I am working with. I know what I need to be able to do to accomplish it, I just don't know if it is viable with code.

award

IMO it can work. You just need to provide intuitive feedback to the player. Your visualization could be like Fire Emblem. Color all the spaces the selected ship can move to. When the player hovers over a space, show the route the ship would take to get there with a long bendy arrow.

To help visualize the "turning" cooldown, you could put a little icon over every spot a turn would be made to get to the location. Or maybe you could even show a "ghost" of the ship navigating the route.

If the player can't reach a position, but hovers over it with a ship selected, show them why they can't reach it by drawing the route to the closest location to it that they could reach.

I think this all could be done without sacrificing the flexibility of your variables. You just need to figure out how to calculate all the navigable spaces. Brute forcing a flood fill might be good enough.

One other thing: I think you should also account and allow for a movement of zero spaces if necessary to turn. It would be silly if you were right next to your target but you had to move away from it because you couldn't turn yet! As long as you find a good way of communicating everything to the player through the UI, I don't think your idea is too complicated for them.

xRegnarokx

award Yeah, so those are all good ideas, and what I am thinking. I was thinking Fire Emblem esq for the highlighted tiles and move arrow.

I have toyed with the ghost ship aspect as well. Doing turn indicators would be nice.

I don't know if it would be necessary to show them why they can't get there since it is a spaceship game there are no terrain barriers.

That is the crux of my issue, how to go about calculating the movement. (Also being right next to the unit and having to move away isn't an issue since it is a space game where your ships can fire from a distance, no need to be next to the unit). Because of the rotation and hexgrid aspect I am struggling to figure out how to create a code that can calculate the movable tiles. Like I said if I manually enter all tiles coords relative to the ship I can get the results I want with a massive convoluted code. I am unsure though how to find movable tiles without doing that.

If I jettisoned the turn cd that would get rid of one of the large strategic aspects. Since there isn't terrain advantages (being in space). However, doing the movement like I have now isn't intuitive for players.

award

xRegnarokx

I don't know of any algorithm which does exactly what you want, so you'll either have to write your own or modify one. Flood Fill is probably a good starting point.

https://www.gdquest.com/tutorial/godot/2d/tactical-rpg-movement/lessons/06.game-board-and-flood-fill/

When filling an adjacent hex, in addition to checking collision with that tile (there can still be enemy ships and such to collide with, right?) you need to also check if you are able to turn. Repeatedly tick down your turn counter as you tick down your range in the algorithm, You probably also need to still consider flooding tiles that were already visited if either you've reached it faster or reached it from a different direction.

xRegnarokx

award okay thanks, I am currently creating code that does what I want but not how I need it to. Using for loops and get_neighbor, once I've gotten it to select the tiles that I need it to I'll probably post it here to give a visual. Also, maybe having a visual might help me figure out how to tweek it to work.

As far as collisions go with other ships I haven't yet fully decided what to do, I'll probably have them to try and simplify for players.

xRegnarokx

award xyz

So, this is so far what I've worked out, though I have yet to figure out how to get the third rotation and possible further rotations for possible higher variable values. This allows for the rotation left and right from the starting position and also the second rotation left and right after moving the required distance. I am still working on how to calculate for 3rd, 4th rotation possibilities.

func test_hex(shipPos):

	var ship = local_to_map(shipPos)
	var shipFace = snapped($Ship.transform.x,Vector2(0.5,0.5))
	
	const faceN = Vector2(0.5,0); const faceNE = Vector2(0.5,0.5)
	const faceSE = Vector2(-0.5,0.5); const faceS = Vector2(-0.5,0)
	const faceSW = Vector2(-0.5,-0.5); const faceNW = Vector2(0.5,-0.5)
	
	const SW = +Vector2i(-1,1); const NW = +Vector2i(-1,0); const N = +Vector2i(0,-1)
	const NE = +Vector2i(1,-1); const SE = +Vector2i(1,0); const S = +Vector2i(0,1)
	
	var face : Array = [null,faceN,faceNE,faceSE,faceS,faceSW,faceNW,null]
	var left : Array = [SW,NW,N,NE,SE,S,SW,NW]
	var dir : Array = [NW,N,NE,SE,S,SW,NW,N]
	var right : Array = [N,NE,SE,S,SW,NW,N,NE]

	var shipRot = 2; var rotCd = 0; var maxSpeed = 5

	var cellPosD = ship

	for a in get_used_cells_by_id(0,0,Vector2i(1,0),0):
		set_cell(0,a,0,Vector2i(0,0),0)
		
	for b in maxSpeed:
		var moveable = Vector2i(1,0)
		var i = face.find(shipFace)
		var rotateR = cellPosD; var rotateL = cellPosD
		var rotCdR = rotCd; var rotCdL = rotCd
		var rotate

		if get_cell_atlas_coords(0,(cellPosD + dir[i])) != moveable:
			set_cell(0,(cellPosD + dir[i]),0,moveable,0)
			cellPosD = cellPosD + dir[i]
			
		if rotCdR == 0 and rotCdL == 0:
			for numb in maxSpeed - b:
				if Vector2(ship).distance_to(Vector2(rotateR + right[i])) >= shipRot:
					rotate = true
				else:
					rotate = false
				if get_cell_atlas_coords(0, rotateR + right[i]) != moveable:
					set_cell(0,(rotateR + right[i]),0,moveable,0)
					rotateR = rotateR + right[i]
					if rotCdR != shipRot:
						rotCdR += 1
				if get_cell_atlas_coords(0, rotateL + left[i]) != moveable:
					set_cell(0,(rotateL + left[i]),0,moveable,0)
					rotateL = rotateL + left[i]
					if rotCdL != shipRot:
						rotCdL += 1
				if rotCdL == shipRot and rotCdR == shipRot:
					rotCdL = 0
					rotCdR = 0
				if rotate == true:
					var extRotL = rotateL; var extRotR = rotateR
					for numb1 in maxSpeed - (numb - b + 1):
						if get_cell_atlas_coords(0, extRotL + left[i-1]) != moveable:
							set_cell(0,(extRotL + left[i-1]),0,moveable,0)
							extRotL = extRotL + left[i-1]
						if get_cell_atlas_coords(0, extRotR + right[i+1]) != moveable:
							set_cell(0,(extRotR + right[i+1]),0,moveable,0)
							extRotR = extRotR + right[i+1]

xyz

xRegnarokx The movement rules are not entirely clear from your initial description. At least I don't get it... So player can (or must?) move in one direction for exactly (or up to?) N hexes. Then they must (or can?) turn exactly once (or multiple times?), then they must (or can?) move in the new direction again for (or up to?) N hexes etc.. This sounds very complicated and kind of restrictive for a single turn movement pattern.

Whatever it is, it surely can be implemented but try to define and write down the rules as precisely as possible, and maybe make some visual schematics of the whole thing.

xRegnarokx

xyz So, the ship may rotate once, left or right. If they rotate they cannot change move direction for N hex. Rhey are free to choose to rotate or not, and they can move more than N hexes before rotating.

In my head it is like rotate is a skill with a cd. Except instead of seconds or rounds it is reset by movement.

Example:
Player ship has a ship with N rotation cd. Player moves 3 hexes and then rotates left. Now the player must move N hex in direction before rotating left or right.

This is a simplified version of what I was originally thinking.

However, what I am trying to implement with take the calculations away from the player, they will have their available move locations highlighted, and an arrow will follow the cursor to show the route the ship will take to get to those positions.

xyz

xRegnarokx Do you have this movement system implemented yet (without range highlighting)? I'm interested in seeing how you solved the issuing of movement orders via user interface.

xRegnarokx

xyz I have it implemented where I have a ship UI that controls rotation and accel/decel. So, the map calculates the movable hexes in a straight line, the ship signals the map to update whenever it moves.

The ship calculates current speed which is sent to the map which uses a for loops.

For speed in current speed:

Which takes the ships transform.x and uses that to call_neighbor in the correct direction, this is reiterated the number of times as current speed to produce highlighted tiles in facing direction.

For rotation I have a simple button UI that when pressed sends signal to player which calls ship, ship rotates and sends signal to deactivate rotation buttons.

In the ship script I calculate how far the ship moves and subtract that from rotation cd to 0, and if 0 calls ship UI to reactivate rotation buttons.

Player scene controls moving with right clicking on highlighted tiles.

xyz

xRegnarokx I was more interested about how it looks from your game player's perspective, not the implementation details.

xRegnarokx

xyz ahh gotcha, so there is the ship and bottom middle of the screen is a control panel with four buttons; two rotate, and two Accelerate/Decelerate, when you accel/decel the hex will light up since your ship is now moving. When you rotate the ship the rotate buttons become deactivated and their visuals change to indicate. (If I were to keep this format I'd put a cd timer on the button). You move the ship by right clicking.

When I was doing that design I was thinking FTL style control bar.

xyz

xRegnarokx I still don't get how this movement is supposed to work. How the player executes a move? How many times they need to click on map hexes or buttons to consume their movement/rotation points in one turn?

The code looks too complicated for what it's supposed to do. Making a solution that works only for specific number of instances of something (in your case rotations) with expectations to later manually expand it to cover couple more such instances is not a good approach to solving a computing problem. A solution should always be generalized and work for any number of instances, following the famous zero-one-infinity principle.

In accordance with this, generalized flood-fill-like algorithms are best implemented in recursive stack-based fashion.

xyz

xRegnarokx Regardless of what your exact movement details are, a generalized flood fill algorithm to get all reachable locations from a starting location would go like this:

push the starting location on the stack

while there are locations on the stack:
	pop a location off the stack
	add it to reachable locations list
	push on the stack all locations that are directly reachable from this location and were not previously visited

your reachable locations list should now contain all reachable locations

xRegnarokx

xyz Thanks for the response.

So, for the first part, about the player executing movement, all they will have to do is right click where they want to go. They'll click once, the ship will move there and the code will handle the calculation for rotation and movement. I am trying to keep it as simple for the player as possible. The player can choose to click a few tiles at a time rather than go straight to the final destination if they want, but that is optional.

For using flood fill, I looked into it trying to figure out implementing it, for me I guess when I was looking at it I was having difficulty visualizing how I was going to restrict it to my specific parameters. Maybe, now that I have a code that does what I want, if I look into flood fill I can better visualize how to use it for my purposes.

Because, if it is a basic movement system I understand how flood fill works, I'm just not sure how to restrict the movable tiles into my more complicated movement system.

xyz

xRegnarokx So, for the first part, about the player executing movement, all they will have to do is right click where they want to go. They'll click once, the ship will move there and the code will handle the calculation for rotation and movement. I am trying to keep it as simple for the player as possible. The player can choose to click a few tiles at a time rather than go straight to the final destination if they want, but that is optional.

Then what's the purpose of having this complicated rotation/cooldown system as a mechanic if the player will be made oblivious of its rules and on account of this couldn't really use it as a tactical element. I'd suggest just abstracting it away and using standard hex-to-hex movement instead.

Beware that implementing any tilemap range calculations without maintaining a stack will result in needlessly complicated spaghettified code.

xRegnarokx

xyz They will be aware of it, first off their allowable movement will calculate that, thus limiting how their ships can move/turn.

Also, there will be an indicator that follows the mouse cursor indicating when the ship would turn, and controlling the ships available paths based on speed, acceleration and rotation.

There will also be this information available to the player while choosing their ships.

So they can use it as a tactical element due to choosing their ships, knowing certain ships can rotate faster, and see it visually in the highlighted hexes, and the arrow that'll show the ships path to the hex so you can decode on the angle you want it facing.

xyz

xRegnarokx If I try to put myself in your player's shoes - this sounds complicated and unintuitive. And on top of that you have problems implementing it. I'd make sure it's really worth it by trying to prototype it on a physical board, get some friends to play it. If it fails there, making it digital could hardly salvage it.

Anyway if you really need practical help with this, make a document that describes this movement system in detail, as if you were writing a rulebook. You'd need to do this anyway for your players. All your descriptions so far are not 100% clear, at least not to me.

The problem is fully solvable by implementing a flood fill traversal of one kind or another, depending on movement rules. It will also result in least amount of code.

Seeing the kind of problems you periodically ask about here on forums, I'd advise to try to finish a simpler, formulaic hex based game first, to gain some experience with implementing all the basics from start to finish, like one level Panzer General or Slay clone. Then proceed to tackle more complex projects.

xRegnarokx

xyz Thanks for all your advice.

So, as far as prototyping it has sort of already been prototyped. I was inspired to use this movement style from a game my friends and I used to play when we were in middle school. Though I have extremely simplified it, the game we played had a much more robust movement system. We all really enjoyed it and the tactical aspect that it brought.

I guess for me because I already understand it, it seems simple. At this moment my rule book would say (This ship must move x before it can rotate, after every rotation the ship must move x again before being able to rotate.) This would be the simplest way I can describe it.

Okay, I'll dig into flood fill again and see what I can come up with. I guess I am struggling due to most examples (and those I've implemented) of flood fill have been very basic. The only variable really being the max distance the unit can move. So, for me to restrict direction, distance, and also an incremental rotation makes me imagine a flood fill that ends up having aspects of the code I already have, which seems convoluted.

I have worked on some small projects like that before. However, I struggle with making things I don't have a clear vision for. That is one reason I chose this project, because I have a vision for what I want to accomplish, and because of that the added motivation as I wrestle through some difficult (for me) concepts to implement.