• Optimize a script

I have made something, it works, but sometimes the system doesn't found the closest point, especially the blue box in the upper left, the one which collide with nothing (that's why i have no A* path).

Time take 5 ms to execute this code below:

for newPtMap in pointList:
		for astarNodeMap in nodeGrid:
			var testPointMap = instanc.get_point_position(astarNodeMap)
			
			var testBox1 = Rect2(newPtMap - Vector2(1, 1), Vector2(3, 3))
			var testBox2 = Rect2(testPointMap - Vector2(1, 1), Vector2(3, 3))
			var item1 = [mapNode.map_to_world(testBox1.position), mapNode.map_to_world(testBox1.size)]
			var item2 = [mapNode.map_to_world(testBox2.position), mapNode.map_to_world(testBox2.size)]
			var testBoxWorld1 = Rect2(item1[0], item1[1])
			var testBoxWorld2 = Rect2(item2[0], item2[1])
			
			if testBoxWorld1.intersects(testBoxWorld2, true):
				var id1 = instanc.get_closest_point(newPtMap)
				var id2 = instanc.get_closest_point(testPointMap)
				instanc.connect_points(id1, id2)

With all informations you give and my personal test, i'm lost. I need something reliable. So what possibilities we have, what is the most reliable and faster ?

  • xyz replied to this.

    TwistedMind Honestly, I think you're trying to punch above your current weight with this project. Which is ok for learning new things but may lead to frustration when too much
    stuff piles up. May I suggest that you take a break and try to finish a smaller, simpler project. Then return to this after some time and experience build up. The unit movement system used in Arsenal is actually quite complex and not at all trivial to implement.

      I'm sorry but, for personal reasons, i MUST succeed.

      Otherwise I have to delegate this part to someone else and when it's for commercial purposes, it's very complicated to find someone with good will. The first prototype has seduced a dedicated community, i can't give up now.

      Edit: or, maybe think about a movement system more simple, if it's possible.

      as long you are tied to Godot 3 you cant use the modern navmesh system ... that's a shame because it would solve all your hassle here

      Pathfinding is always a complex thing. In RTS games it has to be good becaus its all the bread-and-butter. I think a-star is by far the simplest approach to that.

      If you ask me for my two cents ... take your last working approach of your update routine ... try running it in a seperate thread (this isnt so simple either) and leave at it is for now!
      Put it on the CBB-List (CBB = could be better) and do all the other work that has to be done. Get some distance to the problem and refine it later!

      This is always like that...

      Many people invite me to give up. And curiously, one event in the time or the "good person" allow me to solve the problem. I observed one thing in common with these people: they give information and they expect the applicant will understand in one-shot, if he doesn't understand after two or three time, they suggest to give up, because they have difficulties to go at the bottom of things.

      Last Friday, i see someone, in another forum, ask a question about the difference between rigid body and soft body. One "colleague" says rigid body will "simulate" rigid objects like a stone but it will not deform and the soft body "simulate" soft objects but the colleague estimated it's not necessary to specify soft will deform. He gives that information in one line, the applicant doesn't understand well, so i make an answer with a range of 4 lines with more concrete examples, he understands.

      I just have used another words but the message was identical, why does he understands me and not my colleague ?

      Sometimes i wonder if this majority of people realize they speak to others like they speak to themselves, are they afraid of something when they make an answer ? Are they afraid to have an headache or hurt they fingers ?

      If these people expect the applicant will understand information without complete explanation, it's like trying touch something he can't see...
      And so, the caregivers will be frustrated to waste their time, because they don't take the time to avoid waste of time through their answer. They don't help themselves to this.

      When someone says something like "Do a simple line vs box intersection test instead.", ok, right...

      • What exactly the goal of this method ? This is a great keyword for google and allow me to "see" the idea
      • What benefit i will have to use that ?
      • What i will obtain ?
      • What the tool allow me to set up/implemant that ?

      These information missing, so i can suppose all i want and go to the wrong way. Why @xyz afraid to say more ?

      This is the same for "caching": says something like "This can help but must not help in your case." contradicts the idea and again, technical informations missing. What i'm supposed to understand ?
      So these people feels to waste they time and everybody be frustrated.

      as long you are tied to Godot 3 you cant use the modern navmesh system ... that's a shame because it would solve all your hassle here
      Pathfinding is always a complex thing. In RTS games it has to be good becaus its all the bread-and-butter. I think a-star is by far the simplest approach to that.

      What allow you to think the navmesh system is better for a procedural generated map ? For me, navmeshes is suitable only for handmade map, is it possible to adapt navmeshes for any map ?

      Why do you consider Astar system isn't the best approach, why this system is present them ?

      Do you realize if i change the version of godot when a new version coming, i will always waste time to adapt the news features, in or out, the code ? What append if i encounter a "bug" or something incompatible with my material which disallow to move on ? Does i need to "give up" ?

      edit: i found a way that solve my problem, it's effective and low cost but i'd like to understand this story of line vs box intersection test before to share it.

        Hi TwistedMind ... chill out ... you seem frustrated ...

        Maybe you have more skills to teach people than others ... well, then be proud of it, but dont expect other to be when its not there profession.

        I think @xyz spend a decent amount of effort onto your problems, no need to put the blame on him. Maybe he has problems of his own and cant affort more time on this.

        TwistedMind When someone says something like "Do a simple line vs box intersection test instead.", ok, right...

        Well we all assume some knowledge from the other ... line vs box isn't very exotic ... google search would have give you source code in minutes

        What to do with it ? ... well thats a valid question ... but please! respect the time of someone trying to help you. You could have been less demanding and could have been more polite.

        TwistedMind This is the same for "caching": says something like "This can help but must not help in your case." contradicts the idea and again, technical informations missing. What i'm supposed to understand ?

        Well ... at first, i only know a fraction of your project, so im not certain if this is a method to go for you. You have to try to know if this may help with your performance problem, but it may not speed up this algorythm .... i just wanted to warn you that this may result in a lot of effort without any gain.

        TwistedMind technical informations missing

        I made you a drawing and descriped the method ... what do you expect more?

        TwistedMind What allow you to think the navmesh system is better for a procedural generated map ? For me, navmeshes is suitable only for handmade map, is it possible to adapt navmeshes for any map ?

        In godot 4 navmeshes can be generated in runtime ... so educate yourself first!

        TwistedMind Why do you consider Astar system isn't the best approach, why this system is present them ?

        You ask for a simpler approach .... i told you that a star seems to be the simplest .... dont ask if you dont want answers! I wont discuss the pros and cons of navigation methods. There will always be more then one method because there is no perfect one.

        Edit: or, maybe think about a movement system more simple, if it's possible.

        TwistedMind Do you realize if i change the version of godot when a new version coming, i will always waste time ...

        Didnt told you to switch ... was just a chit chat annotation, even if i was ... you could have just sayid"im sorry, i cant switch by now, bacd luck for me!"

        I have give you my honest opinion ... i'm programming for over 30 years ... sometimes take a step back and let some time pass maybe opens up more solutions later on!

        I will leave it by now ... just have to clearify some things.

                    Hello,

                    You ask for a simpler approach .... i told you that a star seems to be the simplest .... dont ask if you dont want answers! I wont discuss the pros and cons of navigation methods. There will always be more then one method because there is no perfect one.

                    I admit i have made a mistake of interpretation.

                    I admit too i'm on straddling the words, sometimes.

                    For the rest, i take note.

                    edit:
                    To be complete and not let this unsolved, here i have done:

                    • After the building appear and the new astar points determinated, i make a "perimeter" of x distance;
                    • I filter all invalid cells, like water, rocks, mountains, and i catch the already astar node in a temp list (poolvect2), news astar node included;
                    • With Bresenham, i check from new nodes one by one (except the one currently checked), all possible connections and i connect if no invalid cells;

                    I undestand astar building node choose the path according the minimum number distance, so it's not necessary to absolutely break the connection from the started astar node, this is just new "checkpoints" added in the middle, after all.

                    To allow to connect points, i don't see any solutions than using Bresenham (your version, @klaas) to determine if there are invalid cells in the way or not. The final result give me a performance between 0 and 15 ms, that depend of the size of the perimeter, this is a question of balance.

                    Because not one building will be added, each connections will not always be clear, maybe i should have shown a screen with two added buildings...

                    I don't think this look like "line vs box intersection test", but if it is, so be it.

                    • xyz replied to this.

                      TwistedMind Line vs box test was suggested for breaking existing connections, not for making new ones. Every connection between two A* points can be represented by a line drawn between them and each newly placed building occupies a rectangle (at least according to images you posted). If that line crosses that rectangle then the connection between two points can be broken. Hence line vs box(rectangle) intersection test can be used instead of iterating through cells. It's as simple as that.

                      Btw you should award the best answer to @klaas because they did a great job of optimizing that bottleneck function, which was the main topic of the original post.