Restricting movement based on tiles moved

Question

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?

Livestock

Answer 1

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.

Gilstrap

Answer 2

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.

Transpacific

Answer 3

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.

Livestock

Answer 4

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.

Gilstrap

Answer 5

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.

Livestock

Answer 6

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

Livestock

Answer 7

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).

Livestock

Answer 8

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.

Gilstrap

Answer 9

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.

Livestock

Answer 10

The data should be stored in tree nodes.

Gilstrap

Answer 11

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.

Livestock

Answer 12

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.

Gilstrap

Answer 13

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?

Livestock

Answer 14

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.

Gilstrap

Answer 15

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!

Livestock

Answer 16

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

Gilstrap

Answer 17

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.

Livestock

Answer 18

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

Gilstrap

Answer 19

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

Livestock

Answer 20

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.

Gilstrap

Answer 21

Yeah, I wasn't building this for the context of my game, it was just to generate a random tree. However, I did realize that error where I was appending them to the stack, but never actually attaching them to the MoveTree class. That was an oversight on my part.

I have also been focusing on the data structure, though just using Godot. I used my research on Python data structures as the basis.

I did eventually change it to have this.

current.append(MoveTree.new(current.number + 1)
stack.append(current.left_child)

I did this for both the left and right child as well as the center child. In order to actually connect the children to the previous node and thus create the hierarchy.

Is there a reason you recommend python to do this in other than just trying to remove my thinking from the practical application to my specific game context? Also, there are multiple types of trees, would you recommend I build each type of tree, or do you think understanding and being able to build one type generally equates to being able to build other types?

Thank you again for all your help, and direction, I really do appreciate and it has helped my understanding grow immensely.

Livestock

Answer 22

I recommended Python because it's similar to GDScript but with it you run programs in a simple traditional fashion from the command line interface. You give them some input data, they run once and produce some output. I think that's the optimal environment when learning core programming stuff. GDScript itself is great as a learning language but the engine environment in which it runs can be distracting and sometimes confusing when you need to focus on "boring" fundamental stuff.

As for tree types, yes there are numerous types but they are all special cases of the same thing. Best to implement the most general kind that stores a reference to some per-node data and can have any number of child nodes, from none to infinite.

Once you have the code that can make such a tree, you should add a print function that prints out the whole tree, perhaps in a form similar to Godot's scene tree. After that you can make a generator that builds randomized trees with specified number of nodes, and a search function that traverses the tree and searches for given node data.

Making all this work properly should get you a solid foundation for using trees with various algorithms.

Gilstrap

Answer 23

Okay, I'll use Python to practice tree building with those three objectives.

Definitely the search function will be important, otherwise the tree won't do me much good.

Livestock