• Optimize a script

TwistedMind What exactly are you doing when a building is placed? You should only minimally update the existing A* database. Don't need to rebuild it from the scratch. You also don't need to use Bresenham for checking if an existing connection crosses the building rectangle. Do a simple line vs box intersection test instead.

    klaas Array::append() is slow. It can/should be completely eliminated from the loop. The output array size is known from the start/end points. That array should be typed and its storage pre-allocated.

      xyz
      correct .. and with PoolVector2Array its about 3 times faster:

      func traceLine2(_startPos: Vector2, _endPos: Vector2) -> PoolVector2Array:
      	var startPos:Vector2 = Vector2(min(_startPos.x,_endPos.x),min(_startPos.y,_endPos.y))
      	var endPos:Vector2 = Vector2(max(_startPos.x,_endPos.x),max(_startPos.y,_endPos.y))
      	var delta:Vector2 = endPos - startPos
      	var lineTiles:PoolVector2Array
      	var e:float = 0
      	
      	if delta.x > delta.y:
      		lineTiles.resize(int(delta.x+1))
      		e = delta.y / delta.x
      		for x in delta.x+1:
      			lineTiles[x] = startPos + Vector2(x,x*e).floor()
      	else:
      		lineTiles.resize(int(delta.y+1))
      		e = delta.x / delta.y
      		for y in delta.y+1:
      			lineTiles[y] = startPos + Vector2(y*e,y).floor()
      		
      	return lineTiles

      xyz This is i exactly do in the idea ! But maybe i think it in the wrong way...

      1. When the building is generated, i need to check corners, because i change some tiles to unpassable tiles (we don't see them because is it the same texture but different id);

      if mapNode.get_cellv(ptValid) != 5 and mapNode.get_cellv(ptValid) != 10: both conditions have to be checked ... not good. Better rearrange your tiles for a simple if mapNode.get_cellv(ptValid) > 5 ... would be better

      That's why i must check only id 5 and id 10, id 10 is the unbuildable, but passable, dirt cell. It's better if i do if idToValid.has(mapNode.get_cellv(ptValid)) ?

      1. I add them in the astar Grid instanced (updating the database, i mean)
      2. I need to connect these news nodes to the already existing one and for that, i need to check if the way is clear;
      3. if it is, i connect them, and in the same time i store these points for the next step;
      4. Naturally, now i have new obstacles, i need to check if the existing node still clear (only the one (in the temp stored list) were connectable with the new one)
      5. If the way isn't clear, i must disconnect these points;
      6. If the building is destroyed, i suppose i must do the inverse system.

      With that base, i make the code like this logic. Doesn't it logic ? Would you like i share the complete code of this part ?

      Do a simple line vs box intersection test instead.

      Can you explain ?

      That's why i must check only id 5 and id 10, id 10 is the unbuildable, but passable, dirt cell. It's better if i do if idToValid.has(mapNode.get_cellv(ptValid)) ?

      This .has would lower the performance i guess ... so you shouldnt do this.
      This optimisation is not mandatory. But if you run some thousends of checks it can bring some millisecs if you have only one condition to check against. Therefor you could alter your tileset ... beginning with some tiles that cannot be entered and after them the others. so you check only if id < walkableTileMaxIndex.

      But before you squeeze the last drop of performance out of your loops, think about the overall structure ... can you cache? can you build proxy data that helps to cut the amount of loops?

      Have your tried implementig the new bresenham linetrace from me? how much time does it take now?

      If the time taken is low enough maybe doing it in a thread will make it work fast enough .... this update procedure shouldnt be called so often right?

      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!