I need help with my puzzle game.

Question

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.

Comments

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

---

Thanks for the reply.
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.

---

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?

---

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.
The collision_test() retuns adjacent pieces

---

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:
https://docs.godotengine.org/en/stable/classes/class_astar2d.html
Here is a video that provides code on how to set it up:
https://youtu.be/Ad6Us73smNs?t=376
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.

---

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

---

Three things to help you out:

• 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 Vectors2s to Vector3s - 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.

---

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.

---

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:
        # already been down that road
        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!

---

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

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

---

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. :P

---

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 checkforpath(), but I got an overflow error.

---

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.

---

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():