How to get a thread to repeat something for as long as needed?

[Goodai9]

Godot Version

v4.6.2.stable.steam [71f334935]

Question

Hello, I have array which I want to keep sorted, currently, it is being done with custom_sort() each frame, but as I add content the array grows, it takes time for it to sort. The array does not need to be sorted each frame, but most often as possible, since the array is not overly necessairy for the working of the game, it is okay putting it in a thread. How would I go for this, since threads execute an instruction once usualy, but I want it to continue for as long and fast as it can. Yes I do understand the basics of threads, it is just the continual repeat part,\.

[gertkeno]

You can use a while true: inside of a thread to keep it running forever, and/or check a variable to stop it when the game should end.

However is sounds like a very strange situation to be in, can you describe your problem more broadly; this feels like an XY problem

[Goodai9]

to describe my situation, I have a physics marble run in my game, and I have a leaderboard that depends on an array being sorted by their distance to the end of the race. The leaderboard is only for show.

[wyrframe]

Can you show how you’re currently sorting it, and how many marbles you’re sorting? If your sorting metric is just a number, you should be able to sort thousands of things per frame at no significant cost.

[gertkeno]

I see, that’s good; maybe a semaphore would work better for that situation so you can start a round of sorting/leader boarding at will without blocking?

var sort_semaphore := Semaphore.new()
var sort_thread_continue: bool = true # set false and post to end the thread
func sort_leader_board_loop() -> void:
	sort_semaphore.wait() # wait to start

	while sort_thread_continue:
		player_positions.sort_custom(_your_sort)
		_display_leader_board_updates.call_deferred()

		sort_semaphore.wait() # wait to sort again

---

@wyrframe brings up a good point, make sure you are calculating the distance (squared) of all players before sorting as calculating a distance for each comparison will use significantly more CPU power. Share your code!

[dragonforge-dev]

Is there a reason you can’t do this every half a second? A timer is good for anything half a second or more in length. Unless you have robots playing this who can see things change in the nanosecond range?

[gertkeno]

You wouldn’t want the game to hiccup every half-second, but again I think it the sorting itself can be optimized better. It should be much easier to sort 1000 marble positions than it is to simulate 1000 marble physics bodies, so something is out of wack.

[sancho2]

Is a complete sort the best solution?
Most of the marbles will not be changing their order in a frame. From the point of view of the marble, if the marble in front is different then there needs a sort otherwise no sort necessary.
That said how many marbles can there actually be? Since there is a leader board, I would bet less than 200 so a sort should not be clogging the system.

[baba]

what about doing it in process but with some kind of int tracker to prevent it from running every frame?

like

var i = 0

func process():

i += 1
example()

func example():

if i < 5:

     return
else:

     do calculations

     i = 0

[gentlemanhal]

FYI, you can use get_physics_frames() (or get_process_frames() depending on where you want to run the logic) instead of using your own counter.

Engine

[sancho2]

I mocked up a demo that still uses sorting but only sorts when necessary.
I did this quick and I am not %100 sure it works as I want it to and I would bet that not the most efficient it could be.
The demo creates a dictionary of 6 marbles (1 through 6). They begin with a score of 0 each and each frame there is a chance to add to their score.
It is 1 in 7 chance that scores change. The random value must == 1.
Each frame loops all 6 marbles to check if their score is > the marble previous. If that condition is true then a complete sort is done and no further checks are needed in that frame.
You can see from the output that the sort is only done when necessary.
(I used a seed because it turns out with only 10 laps a 1 in 7 chance doesn’t come up very often)

extends Node2D
var marbles:Dictionary[int, int] = {
	1:0, 2:0, 3:0, 4:0, 5:0, 6:0
}
var leader_board:Array[int] = [1,2,3,4,5,6]
const NUMBER_OF_LAPS:int = 10
var current_lap:int = 0

func _ready() -> void:
	seed(1)	# uncomment this if you want repeatable results
	pass
	
func adjust_leader_board()->void: 
	for n:int in range(5,2,-1):
		var front_marble:int = leader_board[n]
		var test_marble:int = leader_board[n-1]
		
		if marbles[front_marble]  > marbles[test_marble]: 
			prints(marbles, "scores/positions are changed")
			sort_leaderboard()
			return
	pass

func sort_leaderboard()->void: 
	prints("-----> positions changed so need to sort")
	leader_board.sort_custom(func (a, b): return marbles[a] > marbles[b] )
	print("")
	prints(leader_board, "new leader board")
	print("")

# Called every frame. 'delta' is the elapsed time since the previous frame.
func _process(_delta: float) -> void:
	current_lap += 1
	if current_lap > NUMBER_OF_LAPS:
		set_process(false)
		print("")
		print("----------------------finished")
		
		print(marbles)
		print(leader_board)
		return
	var x:int = randi() % 7
	prints(x, "anything but 1 is no change/no sort")
	if x == 1:
		for n:int in range(1,7):
			set_pace(n)
	else: 
		prints(marbles, "same order as last frame (or after sort)")
	adjust_leader_board()
	pass

func set_pace(n:int)->void: 
	marbles[n] += randi() % 6

Here is the output I get:

6 anything but 1 is no change/no sort
{ 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0 } same order as last frame (or after sort)
0 anything but 1 is no change/no sort
{ 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0 } same order as last frame (or after sort)
5 anything but 1 is no change/no sort
{ 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0 } same order as last frame (or after sort)
1 anything but 1 is no change/no sort
{ 1: 3, 2: 5, 3: 1, 4: 5, 5: 3, 6: 5 } scores/positions are changed
-----> positions changed so need to sort

[2, 4, 6, 1, 5, 3] new leader board

0 anything but 1 is no change/no sort
{ 1: 3, 2: 5, 3: 1, 4: 5, 5: 3, 6: 5 } same order as last frame (or after sort)
6 anything but 1 is no change/no sort
{ 1: 3, 2: 5, 3: 1, 4: 5, 5: 3, 6: 5 } same order as last frame (or after sort)
1 anything but 1 is no change/no sort
{ 1: 6, 2: 8, 3: 4, 4: 5, 5: 3, 6: 7 } scores/positions are changed
-----> positions changed so need to sort

[2, 6, 1, 4, 3, 5] new leader board

6 anything but 1 is no change/no sort
{ 1: 6, 2: 8, 3: 4, 4: 5, 5: 3, 6: 7 } same order as last frame (or after sort)
6 anything but 1 is no change/no sort
{ 1: 6, 2: 8, 3: 4, 4: 5, 5: 3, 6: 7 } same order as last frame (or after sort)
2 anything but 1 is no change/no sort
{ 1: 6, 2: 8, 3: 4, 4: 5, 5: 3, 6: 7 } same order as last frame (or after sort)

----------------------finished
{ 1: 6, 2: 8, 3: 4, 4: 5, 5: 3, 6: 7 }
[2, 6, 1, 4, 3, 5]

Like I said, there is little doubt that this can’t be improved on. (and also still not sure it works perfectly, lol)

[walterpalladino]

ased on your logic, do you think could be fired the process based on an event so as an example will only sort when score changed? That way you can use events and the sorting process will be fired based on that and only on that condition.

[Goodai9]

I think you find the issue, it tries to get the marbles distance every swap instead of before. The XY problem was identified.

func _physics_process() -> void:
    for marble in marbles:
        marble.distance = marble.get_distance()
    marbles.custom_sort(custom_sort)
    update_leaderboard()

func custom_sort(a, b) -> bool:
    return a.distance < b.distance

[normalized]

If you’re interested in learning about threads, as an exercise you could implement this as a low priority thread that runs permanently in an endless loop, and executes a single bubble-sort pass in an iteration, if a semaphore permits it.

[sancho2]

I know you have this marked as solved but it is an interesting issue to me and I want to add another demo.
This one does not loop through each marble and does not sort.
It is a kind of linked list wherein each marble contains a link to the marble ahead and the marble behind. When the score changes on a marble it only moves marbles that are effected by the change in score.

extends Node2D
const MARBLE_COUNT:int = 6

var marbles:Array[Marble] = []
const TEST_PACE:Array[Array] = [
	[0,0,0,0,0,0], 		# frame 1
	[-1,0,0,0,0,1], 	# frame 2
	[2,0,0,0,0,1], 		# frame 3
	[0,0,0,0,0,0], 		# frame 4
	[1,0,0,0,0,1],		# frame 5
	[0,0,0,0,5,0], 		# frame 6
	[0,0,0,0,0,1], 		# frame 7
	[0,0,0,0,0,1], 		# frame 8
	[3,0,0,0,0,0], 		# frame 9
	[0,0,0,0,0,0],		# frame 10
]
var current_frame:int = 0 
var NUMBER_OF_FRAMES:int = 10

func _ready() -> void:
	create_marbles()
	init_marbles()

func create_marbles()->void: 
	for n:int in MARBLE_COUNT: 
		var marble:Marble = Marble.new(n)
		marbles.append(marble)

func init_marbles()->void: 
	var n:int = 5 
	while n >= 0: 
		var marble = marbles[n]	
		if n < 5:
			marble.marble_behind = marbles[n+1]
		if n > 0:
			marble.marble_ahead = marbles[n-1]
		n -= 1

func _process(_delta: float) -> void:
	if current_frame <= NUMBER_OF_FRAMES:
		prints("Frame:", current_frame)
	apply_score()	
	current_frame += 1
	if current_frame >= NUMBER_OF_FRAMES: 
		set_process(false)
		show_results()
		return
	pass

func show_results()->void: 
	print("\nResults:")
	print(marbles)

func apply_score()->void: 
	# There is a flaw in that since we are applying scores in order from 
	# marble.index == 0 to marble.index == 5 the lower index marbles will have 
	# their scores applied first. 
	# This means that when a marble is moving down at the same time as another 
	# marble who's index is greater, and the have the same resulting score, 
	# the lower indexed marble will move below the greater indexed marble.   
	# To see an example, set the NUMBER_OF_FRAMES to 2 and set the second 
	# TEST_PACE entry to [-1,0,0,0,0,-1]
	# That will move marble.index == 0 to last place when theoretically it should 
	# be in second last place
	for marble:Marble in marbles: 
		marble.add_score(TEST_PACE[current_frame][marble.index])
		
class Marble extends RefCounted: 
	var index:int
	var marble_ahead:Marble = null
	var marble_behind:Marble = null
	var score:int


	func _init(_index:int)->void: 
		index = _index
		score = 0 

	func add_score(n:int)->void: 
		var new_score:int = score + n
		if new_score != score: 
			score = new_score
			check_order()
	
	func check_order()->void: 
		var jump:bool = false
		if marble_ahead: 
			while marble_ahead.score < score: 
				print("overtaken the marble ahead")
				jump = true
				# store the marble_ahead.marble_ahead in tmp
				var tmp:Marble = marble_ahead.marble_ahead
				_move_me_ahead()
				if tmp == null: 
					break
			if jump: return 
		if marble_behind: 
			while marble_behind.score > score: 
				print("lost ground on marble behind")			
				# store the marble_bheind.marble_behind in tmp
				var tmp:Marble = marble_behind.marble_behind
				_move_me_back()
				if tmp == null: 
					break

	func _move_me_ahead()->void: 
		# store the marble_ahead.marble_ahead in tmp
		var tmp:Marble = marble_ahead.marble_ahead
		if marble_behind:	# if the marble behind is not null
			# the marble behind gets a new marble_ahead
			marble_behind.marble_ahead = marble_ahead
		# the marble ahead gets a new marble_behind 
		marble_ahead.marble_behind = marble_behind 
		# the marble ahead gets a new marble_ahead   
		marble_ahead.marble_ahead = self 
		# we get a new marble_behind  
		marble_behind = marble_ahead
		# we get a new marble_ahead  
		marble_ahead = tmp
		if tmp:
			# the marble that was ahead of the previous marble ahead gets a new behind
			tmp.marble_behind = self

	func _move_me_back()->void: 
		# store the marble_bheind.marble_behind in tmp
		var tmp:Marble = marble_behind.marble_behind
		if marble_ahead:	# if the marble ahead is not null 
			# the marble_ahead gets a new marble_behind  
			marble_ahead.marble_behind = marble_behind
		# the marble_behind gets a new marble_ahead
		marble_behind.marble_ahead = marble_ahead
		# the marble behind gets new marble_behind
		marble_behind.marble_behind = self
		# we get a new marble ahead  
		marble_ahead = marble_behind
		# we get a new marble behind
		marble_behind = tmp
		if tmp:
			# the marble that was behind the previous marble behind gets a new ahead
			tmp.marble_ahead = self
		
	func _to_string() -> String:
		var s:String = "Marble name: " + str(index)
		s += " Score: " + str(score)
		s += "\tMarble Ahead: "
		if marble_ahead != null: 
			s += str(marble_ahead.index)
		else: 
			s += "null"
		s += "\tMarble Behind: " 
		if marble_behind != null: 
			s += str(marble_behind.index)
		else: 
			s += "null"
		s += "\n"
		return s

FWIW and maybe it will inspire.

[walterpalladino]

I understand you, I like challenges too. Why don’t you think in a FIFO queue where you add movements so, you move the first one which entered the queue? Once move, you remove it from the queue and will wait for the next event / tick until the next available movement.

[sancho2]

It depends on how you are getting moves.
I think that you will have to loop through all the marbles every frame to use a queue system. But that is linear and will be very fast.
My first demo loops through all the racers as well.
A little bit of balancing to limit checking to once every n frames and still be workable.

There is one additional efficiency that may be of interest.
The racers are always going to be nearly sorted. The best sort algorithm for that is the insertion sort.
(If ChatGPT is correct) the Godot Array.sort() default sort is Introsort which is a hybrid sort but doesn’t take advantage of the nearly sorted aspect.
So you may be able to speed up the sort rolling your own insertion sort.

But it does look like it is going to be fast enough as is, in any case.