order values from lowest to highest, or from highest to lowest

Started by RemiD, October 12, 2023, 12:42:34

Previous topic - Next topic

RemiD

this shows a way to order values from lowest to highest, or from highest to lowest
;order values from lowest to highest, or from highest to lowest by RemiD (20180328-1333)
;can be useful to determine which is the nearest entity around player (depending on distance), and target this entity in priority
;can be useful to determine which is the last updated entity around player (depending on millitime), and update this entity in priority

Graphics( 854, 480, 32, 2 )

SeedRnd( MilliSecs() )

;to order values (from lowest to highest or from heighest to lowest)
Global orderedscount%
Dim orderedh%(100) ; handle
Dim orderedvalue#(100) ; value

;a list of entities
Global entitiescount%
Type Tentity
Field renderer
Field d# ; distance from player to entity
Field considered% ; false or true
End Type

;create some entities
For n% = 1 To 10 Step +1
entitiescount = entitiescount + 1
ent.Tentity = New Tentity
ent\d# = Rnd( 10, 1000 )
Next
;debug each entity
For ent.Tentity = Each Tentity
DebugLog( Handle(ent)+" | "+ent\d )
Next

DebugLog("")
;ORDER FROM LOWEST TO HIGHEST
;reset considered state of all entities
For ent.Tentity = Each Tentity
ent\considered = False
Next
;reset ordereds
orderedscount = 0
;order the entities by distance (from lowest to highest)
maxloops% = entitiescount
loops% = 0
While( loops < maxloops )
loops = loops + 1
;find the lowest value in the not considered entities
svalue# = +1000000
sh% = 0
For ent.Tentity = Each Tentity
  If( ent\considered = False )
  If( ent\d < svalue )
    svalue = ent\d
    sh = Handle( ent )
  EndIf
  EndIf
Next
;set the entity with the lowest value as considered
ent.Tentity = Object.Tentity(sh)
ent\considered = True
;create a new ordered instance
orderedscount = orderedscount + 1 : i% = orderedscount
orderedvalue(i) = svalue
orderedh(i) = sh
Wend
;choose the lowest distance value and the corresponding entity
svalue# = orderedvalue(1)
sh% = orderedh(1)
;update this entity
ent.Tentity = Object.Tentity(sh)
;entitycolor( ent\renderer, 000, 250, 250 )
;debug nearest entity
DebugLog( entity+Str(sh)+" is the nearest, at "+ent\d+"units." )

DebugLog("")
;ORDER FROM HIGHEST TO LOWEST
;reset considered state of all entities
For ent.Tentity = Each Tentity
ent\considered = False
Next
;reset ordereds
orderedscount = 0
;order the entities by distance (from highest to lowest)
maxloops% = entitiescount
loops% = 0
While( loops < maxloops )
loops = loops + 1
;find the highest value in the not considered entities
svalue# = -1000000
sh% = 0
For ent.Tentity = Each Tentity
  If( ent\considered = False )
  If( ent\d > svalue )
    svalue = ent\d
    sh = Handle( ent )
  EndIf
  EndIf
Next
;set the entity with the highest value as considered
ent.Tentity = Object.Tentity(sh)
ent\considered = True
;create a new ordered instance
orderedscount = orderedscount + 1 : i% = orderedscount
orderedvalue(i) = svalue
orderedh(i) = sh
Wend
;choose the highest distance value and the corresponding entity
svalue# = orderedvalue(1)
sh% = orderedh(1)
;update this entity
ent.Tentity = Object.Tentity(sh)
;entitycolor( ent\renderer, 000, 250, 250 )
;debug farest entity
DebugLog( entity+Str(sh)+" is the farest, at "+ent\d+"units." )

WaitKey()

End()

Midimaster

Please test how many Millisecs() do your algo need on your system and report back. If it is more than 20msec you should think about a better algo!
...back from North Pole.

RemiD

tested on 3 different computers :
0.05ms for 10 entities.
0.34ms for 10 entities.
0.52ms for 10 entities.

knowing that only the entities which are in range are considered, after a distance check (never more than 10 in my game).

also there is no need to run this procedure each loop. it could be run once each second, depending on the game...

so all is well for my game...


but if you have a better method, please show us...

Midimaster

no need for a better algo, if you only check 10-30 entities.
...back from North Pole.

RemiD

finally i don't need this procedure for my game because i only need to target / update the nearest entity (around player).

so i only use this code :
nearestD# = +1000000
nearestH% = 0
;determine which is the nearest entity around player
For ent.Tentity = each Tentity
 D# = Distance2D( player_mesh, ent\mesh )
 if( D < nearestD )
  nearestD = D
  nearestH = handle( ent )
 endif
Next
;target / update only this entity
ent.Tentity = ent.Object( nearestH )
entitycolor( ent\mesh, 120, 120, 240 )