• Optimize a script

With your code, i see a little performance:

  • from my code, i have 110 ms (creating new pairs of points to connect) and 576 ms (disconnect needed points);
  • from your code, i have 60 ms (creating new pairs of points to connect) and 244 ms (disconnect needed points);

During the game, the freezing view time is less longer.

can you cache ? can you build proxy data that helps to cut the amount of loops?

How can we cache something a player choices to add or not ? For the AI, it can maybe be done, because it has a build order, the choice of the location is randomized for each map, so precalculated.
This update procedure will be called more intensively in the start game, yes, more less in the middle game and close to none in the final game, except if the player are too slow and let the AI the time to rebuild his structures.

when saying cache or proxy data i mean ... maybe the map can be split up into sectors and points and connections can be stored in this sectors. if a building gets erected only points and connections of this sector must be checked. This can help but must not.

This update procedure will be called more intensively ...

Yes .. i mean ... your not calling it 5 times a second or so.

The time to calculate is roughly cut in half, this is quit immense. If do the other optimisation i told your, it could easily be only 30 - 40%
If you then run it in a thread your done with it ... the game will not freeze and the a-star map will be updated in less than a second

Aaaah, i see, you mean like a "bunch". But in our case, only the astargrid can be splitted.

However, if the building is placed just on the limit of two "bunchs" and one points is connected to another point from the other bunch ? It's like to pass the entire and unique list...

Ideally, a optimized approach should be to start from the new astar node, check in a "perimeter of x distance/something" to naturally filter all the points but i think it's very important to include all concerned points and this is the real problem ! And we need to include a connectable node which possibly far away from the new nodes.

How can we catch all the connectable points without check all the astar grid ? Is it possible ? This is the "line vs box intersection test" idea ?

edit:

I speak about that with ChatGPT and it give me that code as example, what do you think:

var start_point = Vector2(0, 0)
var test_point = Vector2(5, 5)

var test_box = Rect2(test_point - Vector2(1, 1), Vector2(2, 2))

var line = Line2(start_point, test_point)

if line.intersects_segment(test_box.position, test_box.position + test_box.size):
    print("connectables !")
else:
    print("not connectables !")

See here ... an example for caching (trading memory for performance) ...
Split up your map into a mid-size grid. Every connection must be assigned to the fields list when intersecting (easy with the linetrace you already do).
If you place a new building (green) you only have to check the connections on the lists in B2, B3, C3 and C4.

This can help but must not help in your case. If this is a viable approach strongly depends on your game.

I see... this trick you mention will suit for which type of game ? In my case, it is a strategy game.

I found information about the "line vs box intersection test", concretely, its like the screen below. Seems to be very similar to your suggestion, klaas, but the suggestion of @xyz is interesting.
But some point isn't clear: we agreed one pairs of intersect boxes will be connected, if green and yellow are clean, the case of blue and green shouldn't be connected, despite the condition is true. So what can it be done to avoid that if i'm not supposed to use Bresenham about unpassable cells ?

Next, we have two green boxes, they should intersect but it's not possible with fixes values. So i think i need to use a "multiplier" from distance_to(), but this method return a float value but i know i have a cell size of 32 x 32 and i need a box size of Vector(x, y). I'm not sure to know how to convert the float to a vector.

If i have a distance of... 4.256 -----> 4.256 / 32 = 0.133, ----> 0,133 * (32/2 = center of the cell) ----> So the vector will be Vector2(2,128, 2,128) so Vector2(2, 2) ?

Maybe a method do this automatically joined withdistance_to() ?


    TwistedMind I see... this trick you mention will suit for which type of game ? In my case, it is a strategy game.

    It's universal and only should give you a hint for caching ... it could be used in your update proccedure but have to be implemented deep in your construct. Those boxes in your picture are not uniformly grid based and so are not usefull for this type of caching.

    The line vs rect intersect test is just a bit of math ... i dont know how this can help your in your update procedure ... maybe @xyz can explain his idea

    Next, we have two green boxes, they should intersect but it's not possible with fixes values. So i think i need to use a "multiplier" from distance_to(), but this method return a float value but i know i have a cell size of 32 x 32 and i need a box size of Vector(x, y). I'm not sure to know how to convert the float to a vector.

    I'm sorry but i dont understand your question. This seems to be a vector math problem ... can you descripe this somewhat clearer? or make a drawing?

    It's universal and only should give you a hint for caching...

    We will need to discuss about this later if necessary.

    ...i dont know how this can help your in your update procedure ...
    ... I'm sorry but i dont understand your question...

    If i interpret well xyz suggest, the goal is to connect only intersected boxes, to prevent numerous and energy-guzzling list traversal of Astar nodes, simply.

    But some of these points are far away and may probably be connectable. If i use a static value to draw the boxes, it's sure some points will be passed and it's not i want and need. To solve that, i think it will needed to change the size of the box, according to the distance, to be sure to check if the point is connectable or not by intersection.

    So i suppose i must take each astar node, draw a boxes from each node and the point to test (the new point added from the new building) and see if they have an intersection each other, one by one. If yes, connection must be done, except if a unpassable cell is "on the way"... that point is still dark, because i don't see how xyz imagine to check that.

    i think @xyz means that when you ...

    To disconnect the existing node for unpassable cells to the other existing nodes (if the building is created between these points, for example).

    ... he would use a box for the building and checks if connections (lines) intersect this box. Apperantly there is no native function for that in godot, but here is a ray_intersects_triangle() in the Geometry class. Calling this twice to build a rect should do the trick. This would be faster then trace a line for every connection.

    ray_intersects_triangle() is for 3D Vector, using 3D in a 100% 2D game seems to be dangerous and i see rect2 has intersects.

    Ok, so here exactly i draw manually before. We can see in blue the new nodes which belong to the new building. Now if i do an intersects, some white nodes intersect with blues. So that's means these point will be connected each other.

    But when i will ask the A* path, how can i be sure the way will avoid the new building ?

      TwistedMind ray_intersects_triangle() is for 3D Vector, using 3D in a 100% 2D game seems to be dangerous and i see rect2 has intersects.

      ok ... but there is
      Array intersect_polyline_with_polygon_2d ( PoolVector2Array polyline, PoolVector2Array polygon )
      this may do it.

      in part two of your algorythm you do

      # we take the already connectable list to check if we need to disconnects some of them
      for index1 in range(0, existingPtToCheck.size()):
      	for index2 in range(index1+1, existingPtToCheck.size()):

      wich i understand as check each connection in the astar map for intersection (woith your traceline) to the new building.

      This could be replaced with a line to box intersection test.

      other idea:
      A simpler and faster approach would be to check first if both ends of the connection are above, below, left or right of the buidlings box, then they wont intersect. Maybe this would speed the process up enough so you can skip enough detailed checks with line trace.
      At a certain point reducing the amount of checks will be more costly then just crunching the remaining calculations with brute force.

      red must be checked ... grey wont intersect

      • xyz replied to this.

        klaas A simpler and faster approach would be to check first if both ends of the connection are above, below, left or right of the buidlings box

        Any line vs box implementation worth its salt would have this as an early exit.
        There are number of optimization strategies that can be employed here, including a space partitioning scheme you suggested earlier, but please be aware that @TwistedMind is relatively inexperienced in using complex data structures, so go gently there 🙂

        @TwistedMind In previous thread I suggested to make a generalized Bresenham implementation because you were still figuring it out so code simplicity and generality was a priority. But now that you're somewhat familiar with it and optimizations actually may come into play, you'll need to have two separate versions. One that just directly checks for collisions and exits immediately when a collision is found without building any arrays (as @klaas already hinted before), and the other that returns a full cell path in an array. The former should be used when you only need to check for collisions and the latter for building cell paths from A* checkpoints. They both should be additionally optimized in the way demonstrated by @klaas.

        This is only optimization concerning the Bresenham. You can optimize further, by aiming to call Bresenham as few times as possible. Again, @klaas mentioned some very good optimization strategies, including space partitioning, caching already caclulated cell paths and checking box-vs-line intersections instead of checking obstacles cell by cell.

        And you can always distribute calculations throughout several frames by using threads, as a last optimization resort.

        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.