# I need help with my puzzle game.

Attention Topic was automatically imported from the old Question2Answer platform.

Hello every one. I’m trying to make a puzzle game, but im running into some problems.

In my game only the pieces on the red line should be deleted but it deletes other pieces too, what is the best way to do somthing like this?

The green lines (image 2) are the deleted pieces that shouldn’t be deleted.

What is your code structure like? How are the lines drawn?

timothybrentwood | 2021-05-08 19:00

The lines or pieces are Node2D’s.
When they are Instanciated they are stored in a 2D array. The pieces are aware of what pieces they are connected too.

Gabi | 2021-05-08 20:04

I assume you have some kind of path-finding algorithm that tries to find its way from the left side of the screen to the right side of the screen traveling through those nodes? Can you post that algorithm or show the code responsible for deciding which of those nodes get deleted when your solver thing runs?

timothybrentwood | 2021-05-08 23:22

Yes I have path-finding but its realy bad, and it doesn’t work very well.

``````func get_connected():
for x in width:
for y in height:
if (x == 0 or x == width - 1) and y < height -1 and all_pieces[x][y] != null:
if !all_pieces[x][y].start_piece_test():
continue
if all_pieces[x][y].collision_test():
for i in all_pieces[x][y].collision_test():
all_pieces[x][y].dim()
i.dim()
path_find(i,  null)
pass
``````
``````func path_find(piece, last_piece):
var new_connects = []
var p_connected = piece.collision_test()
for i in p_connected:
if i.matched == false:
for j in i.collision_test():
if j != piece:
if pixel_to_grid(j.position.x, j.position.y).x == 7 and j.end_piece_test():
j.dim()
i.dim()
new_connects.append(j)
destroy_connected()
print("END")

i.dim()
new_connects.append(i)

if new_connects.size() != 0:
for i in new_connects:
path_find(i, piece)
``````

The dim function just dims the pieces a bit and changes the variable matched to true.

Gabi | 2021-05-08 23:47

I think logically what’s going on is you’re traversing all the paths and when you go down a path that terminates, you’re only removing the last node on that path and not all the nodes between the last node and the last known good node (root).

I can’t tell exactly what’s going on because there are a lot of function calls (as there should be) that I don’t know the details of.

Godot has a built in AStar path-finding node. It’s a bit of work to get it set up but it will do the path-finding algorithm for you:
AStar2D — Godot Engine (stable) documentation in English
Here is a video that provides code on how to set it up:
The video shows how to use it with a `TileMap` but with modifications you can use it with any grid-based system - you just need to implement like `world_to_map()` and `map_to_world()` and maybe two other easy functions by yourself.

timothybrentwood | 2021-05-09 00:46

Thank you once again, I will try to use the aStar node, I will update later.

Gabi | 2021-05-09 01:16

• When they call the `astar_node.connect_points(point_index, point_relative_index, true)` function you are going to want to call
that function with the third argument as `false`:
`aStarNode.connect_points(point_index, point_relative_index, false)`.
• In the video they convert all `Vectors2`s to `Vector3`s - this isn’t
required anymore, just use the `AStar2D` node instead.
• In the `astar_connect_walkable_cells()` function they calculate
`points_relative` based on the tiles all around the tile (up, down,
left and right) - in your code you’re going to want to only connect
cells that make sense for your pieces here on a per piece basis. Like
your cross piece should connect up, down, left and right but your L
piece should only connect up and right.

timothybrentwood | 2021-05-09 02:02

I finally got it to work!!!. Those tips and the article were very helpful, but with the aStar algorithm, it finds the shortest path. Is there a way that, I can get all the connected paths?

The faded pieces are the aStar path, I need the pieces in red to also be connected.

Gabi | 2021-05-11 02:47

Ah it’s so satisfying when you get something to work after working on it forever!!
I’m… really sorry you have to see this:

``````func find_alternative_routes(map_position_list:Array):
var all_connected = []
var first_map_point = map_position_list.front()
var end_map_point = map_position_list.back()
for map_position in map_position_list:
if not (map_position in all_connected):
all_connected.append(map_position)

var potential_connected = []
var connected = get_connected_positions(map_position)
# there are potentially multiple paths from the start
if map_position == first_map_point and connected.size() > 1:
set_map_position_disabled(map_position)
potential_connected = check_for_path(connected, map_position_list)
set_map_position_enabled(map_position)
# we have more than just the coming from and going to points
elif connected.size() > 2:
set_map_position_disabled(map_position)
potential_connected = check_for_path(connected, map_position_list)
set_map_position_enabled(map_position)

for point in potential_connected:
if not (point in all_connected):
all_connected.append(point)
return all_connected

func check_for_path(starting_points, known_path):
var potential_connections = []
for point in starting_points:
if point in known_path:
pass
else:
var path_to_end = _get_path(point, known_path.back())
if not path_to_end.empty():
for p in path_to_end:
if not(p in potential_connections):
potential_connections.append(p)
return potential_connections

func get_connected_positions(map_position):
var index = _calculate_point_index(map_position)
var connected_indexes = aStarNode.get_point_connections(index)
var positions = []
for _index in connected_indexes:
var pos = aStarNode.get_point_position(_index)
positions.append(pos)
return positions

func set_map_position_enabled(pos):
var point_to_enable = aStarNode.get_closest_point(pos, true)
aStarNode.set_point_disabled(point_to_enable, false)

func set_map_position_disabled(pos):
var point_to_disable = aStarNode.get_closest_point(pos, true)
aStarNode.set_point_disabled(point_to_disable, true)
``````

It could really use some refactoring but I think it’s bug free. Call the top function with the results of `get_path()` (while still in MAP coordinates!!).

Basically you loop through all the points, if you have more than 2 connections, meaning there’s a potential branch that could lead on an alternative path to the end, disable that point (as to not back track) and try to find a path to the end from the alternative branch.

Lemme know if you need anymore help!

timothybrentwood | 2021-05-11 03:52

Thank you very much for the HUGE help. I’m not sure what to do with the _get_path() func in line 13.

``````var path_to_end = _get_path(point, known_path.back())
``````

Gabi | 2021-05-11 16:35

Ohhh yeah they have their paths as member variables (declared in the class outside of a function so any function can access it). I refactored my code to not use member variables.

Here’s my implementation of `_get_path()`:

``````func _get_path(map_start, map_end):
var start_point_index = _calculate_point_index(map_start)
var end_point_index = _calculate_point_index(map_end)

var point_path = aStarNode.get_point_path(start_point_index, end_point_index)

if point_path.empty():
printt("unreachable", map_start, map_end)

return point_path
``````

Really it should probably be called `get_map_path()` but my naming skills are great.

timothybrentwood | 2021-05-11 22:31

I was able to get it working! Thanks alot for the help.

I also found out, that, if there is a loop, it won’t mark it as part of the path, wich sense.
I tried to add code to the check_for_path(), but I got an overflow error.

Gabi | 2021-05-12 15:28

Nice! So the reason the loop doesn’t register is because the initial connection is disabled before finding the path to the end. So it starts at the point right below it and doesn’t find a path to the end so it’s not added.

I would have to think more about how to solve that. The work would be done in the `check_for_path()` function. If there is a loop, the path length would have to be size 4 or larger.

timothybrentwood | 2021-05-12 16:00

I made a function that somewhat works, but it also adds unwated connections. And its a BIG mess.

``````func check_for_loops(point, known_path, potential_paths, initial_loop):
potential_paths
var connections = get_connected_positions(point)
for i in connections:
if i in known_path:
continue
if i in potential_paths:
continue
potential_paths.append(i)
printt("get_connected_positions: ",i)

if potential_paths.size() > 3:
for i in get_connected_positions(potential_paths.front()):
if i == initial_loop:
print("loop_completed: ", potential_paths)
return potential_paths

if !potential_paths.empty():
check_for_loops(potential_paths.front(), known_path, potential_paths, initial_loop)
return potential_paths
``````

The function is called from `check_for_path()`, I added an `else` after `if not path_to_end.empty():`

Gabi | 2021-05-12 17:41