Restricting movement based on tiles moved

xRegnarokx

So I've been working on hex movement via mouse input in a turn based game. Thanks to xyz I have constructed a flood fill algorithm that visualizes and makes an array of the possible moveable tiles.

I have played around with AStar2D and can move my unit around in this area, however, I have certain move restrictions I'd like to implement, and am not sure what direction to go to implement these.

My issue is I want the unit to have to move at least x in one direction before it can move in another direction. I've thought of ways of using conditions with distance calculations, but that seems like a lot of code to do this.

Any suggestions on what direction to research that might help me implement this?

ParallelBlack

Newbie here, so apologies if any of this is incorrect, but here’s my solution:

Create two integer variables that will define the movement limits, one for x, one for y.
Set each variable to whatever limit you had in mind.
Each tile moved increases the value of one of those variables by 1.
Then an if statement that triggers once the limit for the first variable has been reached, allowing the next to activate.

xRegnarokx

ParallelBlack Thanks for suggestions.

Unfortunately, I have used that method in a previous movement system and it works, but you need the unit to move.

My current system I want to have a route drawn between the unit and the mouse, and then you activate movement. I feel like I could do this with finding distances between tiles and such, however, I feel this method would be quite bloated and am seeing if there are other methods to research that might be simpler.

I tried AStar2D, however, I need to restrict connections between certain tiles, so, I may be able to figure out how to place all those restrictions in AStar2D. However, I wasn't sure if there was a more direct way rather than creating a complicated list of "if" statements in order to determine which points connect with other points.

Thank you for the suggestion, it does work well for what I want if I changed up my system a bit.

xyz

xRegnarokx It boils down to same solution as your previous problem with movement range. Had you implemented a proper search tree for that, it would have solved you both things at once.

xRegnarokx

xyz Are you referring to the fill algorithm which I used to find the tiles that you can move to?

The way I had thought to handle that would be to add another variable to the output array. The way I was thinking about going about this would have made every entrance an array, which I thought would create more bloat in order to search an array of arrays. However, if I were to use that method I could just add the direction to the tiles that don't allow rotating, and add true to the tiles that allow rotation.

I guess I am having difficulty visualizing how I would determine based on the direction that the ship will be coming if the tile allows rotation or not. Since there will be tiles that you can rotate if coming from one direction, but not the other. So, are you saying that I can handle this in my flood fill algorithm? If so, I'll focus on thinking through my flood fill algorithm and how I can set it up to allow for the variables. I have thoughts on how to do that, I just feel like all my ideas are very bloated and repeat a lot of stuff.

xyz

xRegnarokx You need to learn how to implement a proper abstract search tree. Then adapt it for your specific needs. Improvising around it instead won't ever give you satisfactory results and will just cause more and more headache in the long run.

xRegnarokx

xyz sweet thanks for pointing me in that direction, I'll start me research now.

xRegnarokx

xyz I think some of my struggles isn't always on the conceptual basis but on converting the concept into code.

Like with the search tree I understand the concept, but not being able to figure out a non-bloaty way of doing what I need.

While playing with my son I had an idea how to use my floodfill algorithm using the search tree concept to do what I want. I'll mess around with it and see if I can create the search parameters to do what I want.

If I am successful I'll definitely post my code (since I have a feeling it still may be less than ideal).

xyz

xRegnarokx Flood fill is just a special case of search tree but it won't be sufficient to solve this. Neither will be the built in A* support. Because of your movement system specifics, you'll need to maintain a generalized tree structure that holds your moves and then you can implement various search queries into it for multiple purposes (ranges, paths etc...)

If you have trouble implementing a tree, you should perhaps take a basic programming course that's focused on common data structures and algorithms.

xRegnarokx

xyz So my issue is the array I use for the flood fill is only storing the hex position, but that isn't sufficient to do further searching for my movement. So, should I store the required data in the form of a class that I can then just pull the required information from? My issue is how to handle the data transmission in order to implement a search tree. If I have the data I believe I can implement a search tree for what I need. I just am not sure how best to handle the data without causing serious lag issues whenever the code needs to run.

xyz

xRegnarokx The data should be stored in tree nodes.

xRegnarokx

xyz Okay, that is how I have it, but I guess I don't understand how to implement the search tree I need to in order to find my movement restrictions. I was going to use data reference stored based on each tiles position relative to the unit, and then search that data in order to create connecting points using AStar2D, then once that is set up I could have a connection made between my shipUI and the mouse which would create an arrow between the unit and where you want to move by calling the AStar2D path_to_point().

This is how I was thinking about going about it, where I would create the move restrictions within the tile/AStar setup. I guess if I am using the data directly from the unit which is in the node tree I don't know how to interact with a pathfinding algorithm, or are you saying I should write my own?

Or maybe I used poor terminology so I miss communicated what I was trying to say, I am not talking about where to store the original source data, but rather the reference to it in order to pass it into a func() and implement the search tree.

xyz

xRegnarokx You can't use A* here because the movement cost between same two hexes can vary depending on the transient state of the unit (including being unreachable). Godot's A* has nowhere to store that information. You need to build your own tree precisely to use it for pathfinding. If A* could handle it you wouldn't need any trees.

You should first make it work bruteforce and worry about speed and optimization later. If need be delegate to a worker thread and/or write it in C# or native code.

So something like this:

Once per move:

Build a tree of all possible movements.
Store tree nodes in a hash map (dictionary) as well, indexed by hex position

To find the shortest path for moving to some position:

Get all nodes having that position.
Pick the one with smallest movement cost
Backtrack up the tree from that node to root - that's your path.

xRegnarokx

xyz Cool thanks.

Couple clarifying questions, I tried to look up specifically what you mean by tree nodes, and build a tree of all possible movements.

Like as in if moving to x you need to pass through y and z, and then store those three coords in the dictionary?

So, I guess if you could clarify in this context what you mean by tree nodes and build a tree.

Edit: I think I found it, are you talking in terms of tree data structure?

xyz

xRegnarokx I thought we established that tree is a data structure 🙂 Yeah I'm talking only about data structures pretty much all the time.

Can you implement a general purpose tree in Python? If you're not sure, you should first try to do that. Otherwise it will be very hard to move forward with this.

xRegnarokx

xyz I believe I can, but I feel like I should do more research into it. So, that is my next step, polish up tree constructions.

Thanks for pointing me in a direction!

xyz

xRegnarokx What I'm getting at is that in order to implement or adapt any kind of non-trivial algorithm you need to have solid literacy in common data structures. This includes knowing how to implement them and understanding how they're applicable to typical problems. It's not enough to just conceptually kinda grasp them. You need to be able to wield them.

Most problems require simultaneous usage of more than one type of structure. So when you hear something like: "put movement states in a tree and also hold them in a hash map" it should immediately be clear what's talked about.

The structures to get well acquainted with are:

array
stack/queue/deque
linked list
tree
graph
set
hash map

The good thing is that most of them are a special case of another.

So find a decent looking course or tutorial series that shows how to implement and use those structures. Investing time in learning this will launch your overall coding abilities into higher orbit 🙂

I'll conclude with this Linus Torvalds quote:

Bad programmers worry about the code. Good programmers worry about data structures and their relationships

Which is just a modernized version of this famous Fred Brooks wisdom nugget:

Show me your flowcharts (code) and conceal your tables (structures), and I shall continue to be mystified. Show me your tables, and I won't usually need your flowcharts; they'll be obvious

xRegnarokx

xyz Thanks! I'll go down this path, I feel like I understand array, and stack, queue, deque, at least to the level that I can use them to accomplish my goals. The concept of trees is definitely something I need to dive more into, since my research into it thus far has been very intriguing. Also, hashmaps is another thing I'll research as well, after I am comfortable with these two I'll expand to the others. Thanks so much for pointing me in the right direction.

It is difficult for me to know where to start research when there is so much, I can hyperfixate and dive into something if I know where to head. However, with the vast sea of information I wasn't sure where was good for me to study.

Most courses I've taken have talked basics that I understand and use, but haven't talked so much about data structures outside of arrays.

The others I'll need to do research into aswell, though for now I am going to make sure I can wield tree structures.

xyz

xRegnarokx If you search youtube for basic data structures python you'll get a ton of results.

xRegnarokx

xyz Thanks for all your advice, I've been working on trees. Is this a good way to build a tree data structure, I mixed what I learned from the flood fill algorithm in order to build the tree and to place it in a hashmap. Here is the code, if you get a second and could let me know if I am heading in the right direction. It returns what I expected/wanted from my test.

class MoveTree:
	var number : int
	
	var left_child = null
	var right_child = null
	var center_child = null
	
	func _init(num):
		number = num
	
	func append(child):
		if self.number % 2 != 1:
			if left_child == null:
				left_child = child
			elif right_child == null:
				right_child = child
			elif center_child == null:
				center_child = child
		else:
			if center_child == null:
				center_child = child

var stack : Array = []
var moveTree : Dictionary = {}

var root = MoveTree.new(0)
var dictCount = 0

func _input(_event):
	var current
	if Input.is_action_just_released("left_click"):
		stack.append(root)
		while not stack.is_empty():
			current = stack.pop_front()
			if current.number <= 4:
				if current.number % 2 != 1:
					for x in 3:
						stack.append(MoveTree.new(current.number + 1))
				else:
					stack.append(MoveTree.new(current.number + 1))
				moveTree[str(dictCount)] = current.number
				dictCount += 1
			else:
				continue

xyz

xRegnarokx I don't think your code actually builds a tree. You never call MoveTree::append() so no connectivity between nodes is ever established. I highly recommend you make a generalized tree/node class outside of Godot, so you can concentrate solely on the data structure and not be tempted to quickly shoehorn it into context of your game, before understanding it. That's why I suggested Python. You need to be able to think about data structures in completely abstract way.