Optimize a script

How big is your map? I think you are using the a-star not very optimal.
Usually you would make every tile a point in the a-star-map and disable or enable the points.

okay, i wont dig up this whole conversation, im not totaly convinced with that ... now to the optimisation ... here is my optimised version of your bresenham that is called quit often i guess. Its about double the speed

func traceLine2(_startPos: Vector2, _endPos: Vector2) -> Array:
	var lineTiles = []
	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 e:float = 0
	if delta.x > delta.y:
		e = delta.y / delta.x
		for x in delta.x+1:
			lineTiles.append(startPos+Vector2(x,x*e).floor())
	else:
		e = delta.x / delta.y
		for y in delta.y+1:
			lineTiles.append(startPos+Vector2(y*e,y).floor())
		
	return lineTiles

try it ... how much does this do?

What i did:

• use as many build in function as possible
• try to avoid if statments
• initialise all variables before the loop ... use type hints

If this makes a major impact then you should consider to not call it as a function, do it inline of the other loops as every function call has a overhead. Do not save the result in a array, this has to be created every time, use the loop in the traceline and do the "collision-check" immidiatley

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

listPairId seems some sort of index pairs ...i would avoid using array of arrays ... if you are storing simple id's then use PoolIntArray if possible and store them right after another

This will lead to a very ugly code with lots of repetitions ... but it should be significant faster

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

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?

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?

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

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.