Hi all, I made a post about Astar yesterday, but I found where my issue is so I want to make a new post about specifically that problem.

I have areas of my game where there are separated sections in the navigation. No connections between the areas, but the player can still go between both. There's a gate object that is used to go between the two locations. The red cubes are locations on the astar grid.

When I click on the gate object, it finds the nearest node in the astar grid. But the problem I have is that when I run the code, it always returns the same node. So if I am on one side of the gate, I can get a path to the selected node, but if I'm on the other side of the gate, there is no way to get a path to that node. So it returns an empty path. So I need to figure out how to loop through nodes if a path can't be returned, and I am not quite sure how to do that.

`func get_pathway(start, end):
var gm_start = v3_to_index(navigation_map.local_to_map(start))
var gm_end = v3_to_index(navigation_map.local_to_map(end))
var start_id = 0
var end_id = 0

if gm_start in all_points:
	start_id = all_points[gm_start]
else:
	start_id = astar.get_closest_point(start)

if gm_end in all_points:
	end_id = all_points[gm_end]
else:
	end_id = astar.get_closest_point(end)

return astar.get_point_path(start_id, end_id)`

in the "if gm_end in all_points", how would I loop through all nodes that are within 1 space? That way I can loop through them and check for a path, then return that path.

  • xyz replied to this.

    CorvaNocta How can A* return a path that goes between areas if there are no connections between the areas?

        CorvaNocta I don't really see where's the problem. If you haven't established A* connection between the areas, no path will be returned because a path is basically a list of connections.

            xyz well if I am teleporting the player to a new area, then it becomes a problem. I can no longer move to an object that straddles both areas. If I try to move to the gate from one side of it, it will always return an empty path because the Astar is always grabbing a point that can't be navigated to.

            I did find the get_point_connections func in the docs, but not sure if I am using it right. When testing it doesn't even grab the node that the Astar usually grabs when looking for a connection.

            • xyz replied to this.

                xyz Yes, I understand how it works conceptually. The problem is stemming from having all nodes in a single Dictionary, which creates separated sections. If I wanted to take the time to make hundreds and thousands of Dictionaries I could do that, but it would absolutely wreck my progress. That would take forever. And require even more complex coding than what is necessary, since I would also have to figure out which Dictionary is currently being used. All of that would be massively overcomplicated for something that requires a very easy solution: looping through the other closest points to a location, if I can't find a node connection at the closest move to the next closest. I just don't know how to loop through the nodes that are closest.

                The way this works is to create a single Dictionary that contains all points. And the way my map is set up it will create islands that are not connected to the rest of the nodes. But those islands do have areas that are only separated by the distance of a single node, hence things like gates that can bridge the gap. It should be trivial to find the closest point to a Vector 3, and if that point is not able to create a path look for the closest node that is offset by 1. So if there isn't a connection to the node on one side of the fence, look for a connection to a node on the other side of the fence.

                • xyz replied to this.

                    CorvaNocta The way this works is to create a single Dictionary that contains all points. And the way my map is set up it will create islands that are not connected to the rest of the nodes. But those islands do have areas that are only separated by the distance of a single node, hence things like gates that can bridge the gap

                    That's your problem right here. You need to have A* connections that go through gates/bridges. If you have separate areas of points that are not connected, you're effectively telling to the A* algorithm that there should be no passage between those areas.

                        xyz ok so I have to set it as a disabled point on the gate, to make sure there is still a connection. I suppose I can work with that. If I can't loop through the 8 points that would all be closest to a point, I can settle for needing to create a connection point if that is the only way.

                        Now I just have to figure out how to properly add a point that is disabled! The code to disable a point is pretty simple, wiki covers it just fine, but I am not sure how I would tell the script that a particular node is one that should be disabled. Since I am using the GridMap to create the nodes, that limits my options for what I can do with it. I think I can use Groups to make it work, I'll have to test that out.

                        • xyz replied to this.

                            CorvaNocta No, you don't have to disable anything. Simply make normal connections through gates and maintain a list of all such connections. When a path is returned, check if it contains a connection that goes through a gate. If yes, then proceed accordingly; if the gate is locked - cut the path at that point (or however else you want to handle the situation), otherwise use the full path.

                                xyz It seems like it would be easier to disable the node haha. But ok, I can just keep a running list of points that are locked points, that's pretty easy to do. I can think of a few ways I can make that work. Probably with a second object in my GridMap that can be used for locked nodes would be the best for my situation. I would just need a way to tell the code to put locked objects in a separate list, which should solve that pretty easily. Any suggestions on that?

                                So if I have a path that is going through a locked node, how do I cut it off at the nearest point? After I check if any of the path points go through a locked point, does the "get_closest_point()" still return the closest point to my player or will it still have the same problem where it is always returning the same point?

                                • xyz replied to this.

                                    CorvaNocta No, you don't keep a list of locked points. You keep a list of locked connections, each such connection is a pair of two points. A gate is not a point, it's a passageway between two points.

                                        xyz oh the connections get stored? That's interesting. But I guess makes sense.

                                        So how do you store a list of connections? The connections between nodes seems to just be booleans, with maybe coordinates? How would I store that? And how would I check for connections if I am only given an array of nodes?

                                        • xyz replied to this.

                                            CorvaNocta Query the Astar object. It keeps the list of all connections. It's one of its main jobs. For each connection, I'd store IDs of two points that form a connection.

                                            In fact it's best to do that when making the connections while setting up the Astar object. At some point your code needs to call connect_points() passing two point IDs. So at that time, check if this connection is going through a gate, and if yes, store those two point IDs as a gated connection.

                                                xyz I can definitely create that list with the connections, that sounds pretty easy. The only part I am fuzzy on is how I check if it is a gate or not. The code I have right now just runs through every node and doesn't check for a gate, so obviously I would add in a check, but I am not sure what I am checking for.

                                                #check if this adjacent position is a node
                                                if v3_to_index(v3 + cell) in all_points:
                                                var index1 = all_points[v3_to_index(cell)]
                                                var index2 = all_points[v3_to_index(cell + v3)]
                                                #if they aren't connected then connect them
                                                if !astar.are_points_connected(index1, index2):
                                                #true sets nodes to bi-directional
                                                astar.connect_points(index1, index2, true)

                                                So right after creating index1 & 2 I would throw in a check, "if index 2 is a gate: add that connection to the list" but how do I check if a node is a gate or not? That's the part I am having a hard time figuring out.

                                                • xyz replied to this.

                                                    CorvaNocta how I check if it is a gate or not

                                                    I have no idea. It's your map system. You need to have some way in which you represent/define a gate on the map. How do you put a gate on the map in the first place?

                                                    And again, neither of points should be a gate. A gate is between points (hence it is a connection). Even your map screenshot shows that.

                                                        xyz Well right now the Gate is just an object that is completely separate from the navigation system. The navigation is just a GridMap of cubes (the red ones in the pic) and places where I have something like a Gate or a fence I do not put down a node. So its an empty space as far as navigation is concerned.

                                                        The best way for me to do it would be to add in a new type of cube to the GridMap, a yellow cube perhaps, that denotes something like a gate is there. Which I can add in pretty easily, but I can't pull useful information directly from the GridMap objects. At least I can't find an easy way to. Groups would work best.

                                                        I suppose I could just store objects like the Gate in its own list and make a regular navigation node in the same place. Then just check if the position of that node is the same position as a Gate and work from there. Its a little clunky, but could work.

                                                        • xyz replied to this.

                                                            CorvaNocta Not sure why you insist on putting an A* node where the gate is. The should be between A* nodes. If you have specific type of tiles that contain a gate then you in fact can figure out if there is a gate between two tiles in the gridmap.

                                                            How did you define your fenced areas if there's no conceptions of fence/gate in your map system?

                                                                xyz I thought you were saying I need an Astar node where the gate is to establish a connection? Without that connection, then I wouldn't be able to connect two areas that are split into "islands" right?

                                                                Fenced areas and pretty much everything that is just visual is a completely separate GridMap system. Like the terrain and fences. Anything that doesn't need interaction is on a GridMap, for the most part. If the player clicks on something like a fence I just get the coordinates of the click and the player navigates to the nearest point.

                                                                Gates are Node3D that are not in a GridMap, they are objects I place in by hand. Since the Gates have interaction (like checking for progress in a quest, or a specific item, etc) so they can't be placed using the GridMap. If a player clicks on an interactable object they either navigate to the same cell space, or the nearest cell space depending on what it is.

                                                                The navigation is its own GridMap, completely separate from everything else. it allows me to easily paints areas that are walkable or not by only placing navigation nodes in the places that are walkable.

                                                                I used this tutorial, which works perfectly for me up until this point:

                                                                • xyz replied to this.

                                                                    CorvaNocta I thought you were saying I need an Astar node where the gate is to establish a connection?

                                                                    I said literally the opposite of that.

                                                                    You'll need to go beyond the tutorial. That's why it's important not to blindly follow it but actually try to gain full understanding of what the tutorial is doing.

                                                                    CorvaNocta Gates are Node3D that are not in a GridMap

                                                                    Well then figure out which two tiles are across the gate, get their A* point IDs and you have the connection. Even if you put an additional A* point at the gate position, you'll still need to figure out which tile points to connect to it. It'll just introduce one additional unnecessary A* point to the system.
                                                                    Anyway, the best place to do this is in the code that sets up the A* object. This is probably in the tutorial code, so you'll need to understand it well to be able to append your own stuff to it.

                                                                    Or if you're already painting the navigation using special tiles, you can introduce an additional tile(s) that represent gate connections. But that too will require some interventions into the tutorial code.