I'm trying to replicate the way the Line in the panels of The Witness works.

I got 2 different approaches working one using tiles and another one using a Line2D with a head composed by 4 raycast that collide with the tiles of a collision tilemap.

https://github.com/IIGreed/Witness-Line

The last one is the one that looks the best, because the line doesn't snap from tile to tile it grows as you move the mouse. But snapping the mouse to one axis in order to get the pefect tile cordenades so I can backtrack is giving me some trouble unlike the first Tilemap version and I think that my approach with the raycast is a mess. Does anyone have Ideas of how to improve this?

The problems to solve are: When changing from moving in the X axis to the Y axis the head of the line can get off-center

I guess I could using 8 raycast one on every corner, but this would make fitting into spaces like this where you don't have a corner to align perfectly, hard to fit in.

The reason why the Raycast is so long is because if it wasn't colliding at all times to tell me the distance at times the line go throught the collisions because I was positioning the line pass where it needed to collide.

Other problem is the backtrack but I imagine once I fix the first problem related to the snapping of the line I will always get the same Position when I travel to a tile so I can just check for the last tile in the "route" array holding all the points position and if you are backtracking remove the last point in the line, hopefully this would be seamless and there would be no snapping.

I don't do 2D stuff much.

I don't know that you know about Graph Theory and Data Structure or not, but your project kinda rely on these topics a lot. Might even also need Recursive (function that call itself). I suggest to learn this if you didn't already. I watch its gameplay and the puzzle contain many hidden nodes(graph node, not Godot node).

About backtrack, it is like undo stuff. You should use graph to store history of the line. With history, you can undo history. (Line2D also have some sort of history but not enough information it can store in history, so I recommend to store with data structure)

And about first problem, I don't fully understand, but I think topics above can also help solve this problem.

@sent44
Did you check the project I posted? I just read over the Graph Theory wikipage and it seems like its only useful for placing the: "corners", "nodes", "vertices". It's the base for algorithms like Astar am I wrong? I guess I could try that and interpolate between the path tiles Astar brings back using the mouse motion but the mouse is not free so I would have to set the closest corner based on the mouse movement to the target position or something like that. Does this sound right?

When you talk about hidden nodes are you talking about the vertices or corners in the "tracks" or the elements of the puzzles in the Video of The Witness? I'm not interested in replicating the elements of the puzzle just the way the line works inside the tracks. I think I have an idea of what Data structures are and I use a lot of nested dictionaries and arrays to hold the world info. What you see in the project is a chunk/zone in the world and the idea was to trace a route forcing the player to decide which roads you would visit and which you would miss. I'll read more about the Graph theory maybe I'm missing something.

I made some progress in the project, I got the line to align with each axis, when moving the cursor It will check you are centered on the opposite axis I did this with fmod dividing the position axis by the size of the cell and if the result is half the cell you are good to go, problem is is hard to fit the line in position when you don't have a corner to align perfectly, so I think my next move will be transforming the movement of an axis to another in case the line is not aligned, so it would feel smooth, The Witness also has some kind of easing formula that even if you feed the wrong axis movement it moves the line towards the closest road on that direction.

I think the Ideal and most simple way to solve this would be some kind of rail that turn off and on depending on the mouse movement and this would take care of centering and all that jazz.

No AStar here, or else user path will became shortest path. I only check your project just to play around, not read your code.

Here is section of your map that I badly draw: Well, each (hallway) tile of your map is actually a (hidden) node. 2 nodes that able to connect together become edge. Since you know Data Structure, I assume you already know linked list. In this case will store in linked list like format (store data in graph node itself). You can do this with dictionary, but I recommend to do with (internal class)

class MapNode:
	var position: Vector2
	#var connected_nodes: Array # I know that you will use TileMap.get_cell() to check for connected node, so I comment out
	var next: MapNode

You may now notice that I put node dot in center of each tile, that is actually the position of the node itself. You can now track node path like this

var current_node: MapNode = start_node
while current_node != null:
	line_points.append(current_node.position)
	current_node = current_node.next

Snap problem solve. (Yes, yes, if you use as is, it will be same as first one but it will be line instant of sprite.)

Here is your trackback problem:

var new_input: MapNode = get_map_node_from_position(mouse_position)
if new_input.next == current_last_node:
	# User do trackback event
	current_last_node = new_input
	current_last_node.next = null # Clear connection of user path
else:
	current_last_node.next = new_input
	current_last_node = new_input

The code above can do trackback and draw path. But with a bit of modify, you can also check for path collision. Trackback problem solve.

And lastly, with creative, you can make non tile based map, one way path or (this is what you want) grow and shrink line to cursor. Like add corner_points and last_position properties to MapNode and when you build line you might use last_position instant of position or draw path the same size as hallway with help of corner_points

Thanks for the in depth explanation this looks promising, I've made 3 different methods and all have different pros and cons but none satisfy my needs...

It doesn't matter in which script I put the MapNode class right or should it be its own script? Are you creating the MapNodes in get_map_node_from_position(mouse_position) or did you create them somewhere else? and lastly this block of code, is used after reaching a MapNode position, the center of the tile right?

var new_input: MapNode = get_map_node_from_position(mouse_position)
if new_input.next == current_last_node:
	# User do trackback event
	current_last_node = new_input
	current_last_node.next = null # Clear connection of user path
else:
	current_last_node.next = new_input
	current_last_node = new_input

I'll give it a go tomorrow I'll have to read about inner classes because I've never used them.

I recommend put MapNode in same class(.gd file) that has line system but it can also be its own class (in it own .gd file) with class_name MapNode And about the node data itself, I forgot to mention this, you need to initialize(create) it first and store in (2d) array. Since I forgot to mention this, I will show you with cool tick with dictionary instant

var map_data: Dictionary = {}
func _ready() -> void:
	for x in range(map_size.x):
		for y in range(map_size.y):
			var node: MapNode = MapNode.new()
			node.position = Vector2(x, y)
			map_data[Vector2(x, y)] = node

get_map_node_from_position() is function that get mouse position in, convert its position to world map position, fetch(not create) MapNode node from map_data with converted position and return that node.

and lastly this block of code, is used after reaching a MapNode position, the center of the tile right? It should be use when mouse pointer point to another tile from current one. In fact, you should do like this

if new_input == current_last_node:
	# The mouse still stay at the same node (it might move a bit), so do nothing.
	pass
	# Or just update its last_position
	#current_last_node.last_position = mouse_position

when mouse move(input) or every frame(process).

I got the lines going and the backtrack kind of... but it seems I'm not disconnecting the nodes properly. I'm getting really confused about how the chain of nodes work. Is MapNode.next suppose to point to the previous node in the path or to the node you are going to?

https://github.com/IIGreed/LineGraphTheory As it is no better than my first attempt using tiles t_t

And also the animation of the line is going to be tricky on straight lines I guess I can just create the point and drag it with the mouse while centering the line on opposite axis. But on corners this is going to be annoying having to change inside the same tile from copying the X axis from the mouse to the Y and make it look smooth like a liquid filling a tube.

I want to say that your code in now very clean and easy to read so I read and modified your code and it is now work properly. (Don't forget to read my comment in code)

MapNode.next is suppose to point to next node, if you want to record backward too, you might want to add previous property.

You can determine which direction between 2 nodes with node.next.position - node.position, I don't know if this is what you want.

Off topic, I expect you to construct the line every time the thing change with

var current_node: MapNode = start_node
while current_node != null:
    line_points.append(current_node.position)
    current_node = current_node.next

But you just add or remove the last point, which is also work, but also better optimize too. Good job ;)

@Megalomaniak Huh, how?, Is it post link directly?

Yeah I just posted the link here is the plaintext of that post:


Note that you can embed pastebins directly in here:

https://pastebin.com/pnZmZjCf

We also added the same kind of embedding for github gists as well.

Thanks! I added back:

elif current_last_node.chain.has((new_input.position+line_offset)/cell_size):
 	current_last_node.next = new_input
	current_last_node = new_input
	add_point(new_input.position)

Otherwise you could skip tiles if you hovered over a non adjacent tile which is pretty easy to do in corners. I'll leave it a that for now and implement it into the game, and I'll worry about the line animation on a later day Thanks again for your time and patience.

Remember #var connected_nodes: Array? This will solve that issue without workaround.

Yes, chain is connected_nodes I just changed the name

var node: MapNode = MapNode.new()
node.position = Vector2( x * cell_size,  y * cell_size ) - line_offset
node.chain = get_adjacent_cells(x,y) 

func get_adjacent_cells( x, y ) -> Array:
	var array:Array
	for dir in [Vector2.UP,Vector2.LEFT,Vector2.DOWN,Vector2.RIGHT]:
		var next_cell = Vector2( x, y )+dir
		if map.get_cellv(next_cell) != -1:
			array.append(next_cell)
	return array
2 years later