Sort actors algorithm comparison


#1

This is a piece of code for testing Sk features and functionality, not intended to be a piece of code to be used in a real product. That said, I tried to compact the code as much as I could, and wrote it as cleanly as I could. Comments are welcome.

It takes a list of actors and sorts them by weighing each actor using a formula that takes into account the players facing direction and distance. Using the weight results it creates a sorted list of actors.

In blueprints (probably illegible but the point is to see the complexity, not read it precisely):

Here is the equivalent code in Sk:

    &blueprint
    (Vector3 playerLoc, Vector3 playerFwd, Real maxRange, Real maxAngle, Real weightDtoA)
    [
      @output_list.empty
      !costList : Real{}
      @actor_list.do (Actor currentActor)[
        !cost : weightActor(currentActor.actor_location(), playerLoc, playerFwd, maxRange, maxAngle, weightDtoA)
        !idx : 0
        if costList.any?[idx++ cost < item ] [costList.insert(cost, idx) @output_list.insert(currentActor, idx)]
        else [costList.append(cost) @output_list.append(currentActor)]
      ]
    ]

Obviously, the Sk version is a lot more compact, and unlike blueprints, I can debug it while it runs on standalone or console, and runs a lot faster than blueprints. It also avoids losing time trying to wire things up so it doesn’t spaghettify, laying out re-route nodes, etc. As we can see here, sharing BP is a pain because it’s visual, it’s hard to break out code snippeds with jpgs, and make changes and share. Not to mention that following all those wires to make sense of the algorithm is much much harder than reading Sk.

Over C++ the advantages are similar. Less overhead adding UPROPERTIES, and depending where I want the code, exiting Unreal might be necessary in C++. With Sk I can debug in Release or Shipping, whereas in C++ it can be difficult or impossible (code gets optimized out or moved around, and debug symbols are missing so watch values are unreliable). A related consequence is that in C++ performance testing is unreliable in Debug but Debugging is hard in Release. Sk allows reliable debugging in Release so you can do both test performance and allow reliable debugging.

As a test of using Sk classes I made the same algorithm using a class that stores the costs and actors in it, which is less practical, but I used it to learn how to work with Sk classes.

    &blueprint
    (Vector3 playerLoc, Vector3 playerFwd, Real maxRange, Real maxAngle, Real weightDtoA)
    [
      @output_list.empty
      !costList : SortData{}   
      @actor_list.do (Actor currentActor)[
        !listItem : SortData!
        listItem.@cost := weightActor(currentActor.actor_location(), playerLoc, playerFwd, maxRange, maxAngle, weightDtoA)
        listItem.@actor : currentActor
        !idx : 0
        if costList.any?[idx++ listItem.@cost < item.@cost ] [costList.insert(listItem!, idx)]
        else [costList.append(listItem!)]
      ]
      costList.do_idx[@output_list.append(item.@actor)]
    ]

EDIT: Numbers for this algorithm:

PC  | Lang | Console
___________________
 30 | Sk   | 80
104 | BP*  | 433    (5.4x slower)
733 | BP   | 2539   (many x slower)

* with Nativize on (turning BPs into C++)
600 moving actors being sorted O(N log(N))

Skookumscript performance
#2

Cool! Awesome example. :madsci:

I know that the List@any?() method can have an optimization that will make it 2.66X faster. We’ll try to pop that in for you soon.


#3

Make it an even 3X faster and you’ve got yourself a deal, sir! :grin:


#4

Cool - you could still simplify it a bit! In my example below I

  • used the SortData constructor to create a new SortData instance
  • removed unnecessary copy constructors
  • fixed a bug where I replaced idx with idx-1
&blueprint
(Vector3 playerLoc, Vector3 playerFwd, Real maxRange, Real maxAngle, Real weightDtoA)
[
  @output_list.empty
  !costList : SortData{}   
  @actor_list.do (Actor currentActor)[
    !listItem : SortData!(weightActor(currentActor.actor_location(), playerLoc, playerFwd, maxRange, maxAngle, weightDtoA), currentActor)
    !idx : 0
    if costList.any?[idx++ listItem.@cost < item.@cost] [costList.insert(listItem, idx-1)]
    else [costList.append(listItem)]
  ]
  costList.do[@output_list.append(item.@actor)]
]

Interesting, long time ago I actually published an article in Game Programming Gems V called “Fast Target Ranking Using an Artificial Potential Field” describing a similar angle/distance tradeoff formula implemented for Jango Fett in the game Star Wars Bounty Hunter. Good times!


#5

Awesome. That’s as good as that piece of code gets.

This is just for testing, but here’s the very sophisticated (/s) weigh function I’m using:

(Vector3 actorLoc, Vector3 plrLoc, Vector3 plrFwd, Real maxDist, Real maxAng, Real weightDtoA) Real 
[
  !diff : actorLoc - plrLoc
  !dist : diff.length
  !locFac : [dist / maxDist].min(1.0)

  !ang : MathLib.acos(plrFwd.dot(diff) / dist)
  !angFac : [ang / maxAng].min(1.0)
  
  MathLib.lerp(locFac, angFac, weightDtoA)
]

I’m not even checking for bad input values :smiling_imp:


#6

We’ve made this optimization and similar optimizations in related List methods. We’ll make it available shortly.


#7

Thought I should write an update to this. On this sorting algorithm we indeed saw a speed boost or 40% after getting the changes! Making the List@any? method go 2.66x faster has a very strong effect on overall performance. Great job!