Detect the shape of a TPA?

[Floor66]

Hello,

I'm currently analyzing animations on a screen for a browser game, using getShiftedPixels() from here: https://villavu.com/forum/showthread...tshiftedpixels

The result I'm getting until now is decent (filtering by TPA size, sorting from midpoint), but not good enough. I need a way to find out whether the TPA's I find are circular, because those are the only ones I'm interested in.
A big problem is, though, that they aren't perfectly circular: (the red number is the number of TPoints in this TPA).

I need to filter out things like these: , which are similar in size, but absolutely the wrong shape.

Can anyone point me in the right direction?
I've though of perhaps overlaying a circle on the TPA and then looking for 'empty' areas so to say (a circle would cover another circle more than an irregular shape?).
Another thing is perhaps measuring the mean spread between points in the TPA? Help me out here :P

[wallie018]

Maybe you could do something with TPAFromCircle, to make a TPA with circular size, then subtract this created TPA from your detected TPA with ClearTPAFromTPA. If there are a lot of pixels left in the result, this means that a lot of pixels are outside the circular TPA. The more pixels are left outside, the more non-circular your shape is?

[Floor66]

Thanks for the quick reply! I'm gonna test this asap. I think I'll get the midpoint of the TPA and the diameter to create the circle with. Another thing I've been thinking of is TPoint density in the TPA. Dometimes the "artefacts" are quite scattered but still valid in size.

[bonsai]

Those are neat ideas.

Are these circles the same size all the time? You might be able to just use the height and width of getBounds()

[Floor66]

Nope, unfortunately their size varies. They constantly fade in and out in the game (thus the use of pixelShift), and depending on where you get them in their fade-cycle, their size varies slightly.

Now I'm writing this though, they do generally stay in the 150-250 TPoints range all the time... GetBounds is on my list for trying!

Edit: might get a TBox of each and then divide its width and height. A circle fits in a square (-ish) and the abnormal shapes are way more rectangular.

[bonsai]

A circle fits in a square (-ish) and the abnormal shapes are way more rectangular.

That's definitely the thought I had looking at it. Circle/square - same thing.

[The Mayor]

I have no idea if this will work in practice but it's kinda fun. You could estimate how much a TPA represents a circle by calculating its circularity.

Circularity is basically a function of the shapes area and perimeter, which ranges from 0 to 1, with 1 being a perfect circle. E.g.,



First you would have to get the convex hull of the TPA, and then calculate the circularity of that bounding polygon. You can only keep TPAs greater than a certain circularity.

Here is an example. I included a function which converts an ATPA to an array of convexHull polygons. You will have to use the updated function by slacky because srl-6 hasnt been updated yet.

You will see one of the TPAs gets filtered out because it is less than 0.8

program new;
{$i srl-6/srl.simba}

function polyArea(p: TPointArray): extended; //calc polygon area
var
  i, z: Integer;
begin
  z := 1;

  for i := 0 to high(p) do
  begin
    if i >= high(p) then z := -i;
    result += (p[i].x * p[i+z].y) - (p[i+z].x * p[i].y);
  end;

  result := abs(result /= 2);
end;

function polyPerimeter(p: TPointArray): integer; //and the perimeter
var
  i, z: Integer;
begin
  z := 1;

  for i := 0 to high(p) do
  begin
    if i >= high(p) then z := -i;
    result += distance(p[i], p[i+z]);
  end;
end;

function circularity(p: TPointArray): extended; // calc the circularity
begin
  result := 4 * pi * polyArea(p) / pow(polyPerimeter(p), 2);
end;

function T2DPointArray.filterCircularity(c: extended): T2DPointArray; // exclude TPA which are < c
var
  i: Integer;
begin
  for i := 0 to high(self) do
    if circularity(self[i]) >= c then
      insert(self[i], result, length(result));
end;

function T2DPointArray.toConvexHull(): T2DPointArray; // returns bounding points of each TPA, as an ATPA
var
  i: Integer;
begin
  for i := 0 to high(self) do
      insert(self[i].getConvexHull(), result, length(result));
end;

var
  ATPA: T2DPointArray;
begin
  //Return your colours as an ATPA
  //ATPA := ATPA.toConvexHull();

  ATPA := [[[148, 124], [131, 133], [126, 149], [133, 165], [154, 166], [167, 150], [165, 130]], [[2, 3], [3, 3], [3, 2], [2, 2]]];

  writeLn('Length ATPA before: ', length(ATPA));
  ATPA := ATPA.filterCircularity(0.8);
  writeLn('Length ATPA after: ', length(ATPA));;
end.

[Floor66]

I've pretty much nailed it right now. Ended up using a combination of TPA length, TPA diameter and TPA circularity (excellent addition, Mayor! brought the accuracy from like 75% to 90%).

So I'd say ~90% accuracy atm (sometimes it'll take a few scans to find 'em), and <5% false positives:

function findPickups(): TPointArray;
var
  i, w, d: Integer;
  circ: Extended;
  us, tmp: TPoint;
  scanArea, tmpBox: TBox;
  shifts, tmpTpa: TPointArray;
  objects: T2DPointArray;
begin
  scanArea := toBox(game_MSX1, game_MSY1, game_MSX2, game_MSY2);
  shifts := getShiftedPixels(scanArea, 50);
  objects := TPAtoATPA(shifts, 75);

  if(Length(objects) > 0) then
  begin
    if debugPickups then
      etl_ClearLayer();

    SortATPASize(objects, False);
    for i := 0 to High(objects) do
    begin
      if(Length(objects[i]) <= 300) and (Length(objects[i]) >= 100) then
      begin
        tmpTpa := objects[i].getConvexHull();
        circ := circularity(tmpTpa);
        tmpBox := GetTPABounds(objects[i]);

        if(circ >= 0.9) and (circ <= 1.1) then
        begin
          d := Distance(tmpBox.X1, tmpBox.Y1, tmpBox.X2, tmpBox.Y2); //diameter
          if(d <= 25) then
          begin
            tmpTpa := objects[i].getConvexHull();
            tmp := MiddleTPA(objects[i]);
            insert(tmp, Result, Length(Result));

            if debugPickups then
            begin
              etl_DrawTPA(objects[i], clGreen, False);
              ETL_DrawTextEx(tmp.x, tmp.y, 'UpChars', IntToStr(Length(objects[i])) +' | '+ IntToStr(d) +' | '+ FloatToStr(circ), clRed, True);
            end;
          end;
        end;
      end;
    end;

    if findUs(us) then //if we can locate ourselves, get the closest pickup first
      SortTPAFrom(Result, us);
  end;
end;

P.S.: ETL is awesome, it's helped me so much.

[Citrus]

...

EDIT: it was something else causing problems with bitmaps, so the original is fine.

Yay! I'm glad someone is getting use out of the function.
I was having problems with bitmaps not being freed when using getColors(), so you might want to use this (thank you @bonsai)

function getShiftedPixels(b: TBoxArray; time: integer): TPointArray;
var
  orig, curr: TIntegerArray;
  w, h, x, y, i: integer;
  atpa: T2DPointArray;
begin
  setLength(orig, length(b));
  setLength(curr, length(b));
  setLength(atpa, length(b));

  for i := 0 to high(b) do
    orig[i] := bitmapFromClient(b[i]);

  wait(time);

  for i := 0 to high(b) do
    curr[i] := bitmapFromClient(b[i]);

  for i := 0 to high(b) do
  begin
    w := b[i].getWidth();
    h := b[i].getHeight();
    for x := 0 to w-1 do
      for y := 0 to h-1 do
        if (fastGetPixel(orig[i], x, y) <> fastGetPixel(curr[i], x, y)) then
          atpa[i].append(point(x, y));

    atpa[i].offset(point(b[i].x1, b[i].y1));
  end;

  freeBitmaps(orig);
  freeBitmaps(curr);
  result := atpa.merge();
end;

[Floor66]

What'll that new function do for speed compared to the old one? Speed is a decent concern in this script.

[Citrus]

What'll that new function do for speed compared to the old one? Speed is a decent concern in this script.

It seems to be a bit slower, but that's easily fixed by only using every other point, which is what I use in my scripts. This is the only thing that changes:

for i := 0 to high(b) do
begin
  w := b[i].getWidth();
  h := b[i].getHeight();
  for x := 0 to w-1 do
  begin
    for y := 0 to h-1 do
    begin
      if (fastGetPixel(orig[i], x, y) <> fastGetPixel(curr[i], x, y)) then
        atpa[i].append(point(x, y));
      inc(y);
    end;
    inc(x);
  end;

  atpa[i].offset(point(b[i].x1, b[i].y1));
end;

[Floor66]

I'll try to experiment some more... Currently still using the function in its old form, but added 1 line in this loop:

for i := 0 to h do
  begin
    if cols1[i] <> cols2[i] then
      insert(tpa[i], Result, Length(Result));
    IncEx(i, SPEED_FACTOR); //This one 'ere
  end;

This allows me to cut down the time it takes to go through the TPA exponentially, varying by SPEED_FACTOR. Of course at a certain factor, almost no points are looked at, which is garbage. I've found that 5 or 6 makes for very quick scanning and accurate results.

Of course I did have to adjust my TPA length detection criteria to this SPEED_FACTOR (simple division).

EDIT:
Actually, using i := i + SPEED_FACTOR; is about 50% faster than IncEx.

EDIT2:
Could this be made into a plugin? For speed. Right now it's comfortable, but not amazing.

[slacky]

I'll try to experiment some more... Currently still using the function in its old form, but added 1 line in this loop:

for i := 0 to h do
  begin
    if cols1[i] <> cols2[i] then
      insert(tpa[i], Result, Length(Result));
    IncEx(i, SPEED_FACTOR); //This one 'ere
  end;

This allows me to cut down the time it takes to go through the TPA exponentially, varying by SPEED_FACTOR. Of course at a certain factor, almost no points are looked at, which is garbage. I've found that 5 or 6 makes for very quick scanning and accurate results.

Of course I did have to adjust my TPA length detection criteria to this SPEED_FACTOR (simple division).

Tips: Drop the use of Insert when performance is a concern (at least for all loops where you add a lot of points). Even a raw `L := length(arr); SetLength(arr, L+1); arr[L] := item` is quicker. Setting the length of an array will quickly turn into an expensive operation.
You have two good options here: 1. over-allocate; 2. pre-allocate.

Pre-allocating:

SetLength(Result, length(tpa));
count := 0;
for i := 0 to h do
  if cols1[i] <> cols2[i] then
    Result[count] := tpa[i];

Over-allocating (2x) - can be a lot nicer on memory-usage, while nearly yielding the same performance as pre-allocating:

res_hi := 0;
res_len := 512;
SetLength(Result, res_len);
count := 0;
for i := 0 to h do
  if cols1[i] <> cols2[i] then
  begin
    Result[res_hi] := tpa[i];
    Inc(res_hi)
    if res_hi = res_len then
    begin
      res_len *= 2;
      SetLength(Result, res_len);
    end;
  end;

---

The answer given by the mayor is alright - I've offered "TPACircularity" in SimbaExt for years - but nobody cares about SimbaExt: The only usage it sees is people reading through it, or features copied into Simba, and sometimes SRL ^__-

Keep in mind: As Mayors function is actually computing the convex hull before it computes the circularity the result can go bad. Why? Imagine if the shape is a 6-edged star, the convex-hull of it would be a hexagon, what does a hexagon resemble? - A circle.. So it would likely score 0.9+, this can happen with a number of concave shapes.
But this might be fine in your usage (id assume it is). I am just mentioning it.

-----------------
On the other hand based on that you say the other shapes are entirely different, something like this could actually be enough, and much cheaper than most of other stuff here:

function ThingyThatDoesStuff(SolidTPA:TPointArray): Double;
var
  B: TBox;
  rad,area:Double;
begin
  B := GetTPABounds(SolidTPA);
  rad := Max((B.x2-B.x1+1), (B.y2-B.y1+1)) / 2;
  area := Sqr(rad) * PI;
  Result := area / Length(SolidTPA);
end;

Now this doesn't match for a circle, at all - it will yield good results for anything that occupies the same sized area as circle - within a box.
But, by the looks of it, it could work.

PS a good result will be in the range of 1, a square will give about 0.78, something crazy can be 20+ :P

[Floor66]

Thanks for the writeup dude! Yeah 90% of the speed of this script is dependent on the pixelShift function, speeding that up would be awesome. Memory usage doesn't seem a huge problem (yet? :P)

EDIT:
Scratch that. Running out of memory quite quickly when not using insert.

[Citrus]

Thanks for the writeup dude! Yeah 90% of the speed of this script is dependent on the pixelShift function, speeding that up would be awesome. Memory usage doesn't seem a huge problem (yet? :P)

How big of an area are you dealing with? I've been testing it with the RS3 mainscreen and it only takes 9ms. I can't imagine that would be too slow.

[Floor66]

Hmm strange. I'm not finding speeds like that at all. I'm using a 5ms 'time' parameter.

On my laptop it's about a 1500x800 area I'm scanning, which is taking aprox. 50ms.
It usually takes a few passes (4-6) to get all the objects I'm looking for, so about 200-400ms of 'idling' between moving around in the game.

[Citrus]

Hmm strange. I'm not finding speeds like that at all. I'm using a 5ms 'time' parameter.

On my laptop it's about a 1500x800 area I'm scanning, which is taking aprox. 50ms.
It usually takes a few passes (4-6) to get all the objects I'm looking for, so about 200-400ms of 'idling' between moving around in the game.

Why 5ms and not 50 or 100? Is the game updating that fast? It doesn't make sense to only scan for 5ms if the whole process takes 50ms.

[bg5]

You can find middle point of TPA, then count pixels in the circle of radius r. Non-circular shapes will have noticeable less pixels there. You said that size varies, so radius r may be the function of overall pixel count e.x.

r = sqrt( RADIUS_LENGTH_FOR_THE_BIGGEST_CIRCLE^2 - (OVERALL_PIXEL_COUNT_FOR_THE_BIGGEST_CIRCLE - current_overall_pixel_count ) )

You can do it with few native functions, without any iterations in script.


* the equation of r is just a relation: how radius changes when you subtract some value from area of the circle.

[Floor66]

Why 5ms and not 50 or 100? Is the game updating that fast? It doesn't make sense to only scan for 5ms if the whole process takes 50ms.

In 5ms the pixels that I'm looking for have shifted already. That's how fast the animation runs. I'll play with it a bit though.

[slacky]

In 5ms the pixels that I'm looking for have shifted already. That's how fast the animation runs. I'll play with it a bit though.

Curious, what game are we really talking about?

[Floor66]

It's a (flash-based) game called Seafight, which has these 'shimmers' on the map, which are basically free pickups with (premium) currency inside them. See attachment for an example.

Their colour can vary (randomly picked I believe), and they constantly 'shimmer', ergo fade in/out, become a bit brighter/more dim, etc.

Taking a slightly longer pixelShift time and then reducing the amount of passes has won some performance again!

glimmer.png

[slacky]

It's a (flash-based) game called Seafight

Aha, yeah I remember a few users over at SCAR some years ago was playing, and trying to bot that game :P

[Floor66]

I've created a bot now that'll quite accurately seek out and pick up those bonus pickups (the shimmers). I've developed a way of detecting where the player is on the minimap, and using that, picking (randomly, but with some filtering criteria) a direction to sail in, along with a few filters like not sailing left first, and then straight back to the right after, or sailing in the same direction for too long.

The game also has monsters to kill, which just sit still, but are also animated in place. Detecting them will be pretty easy but you don't gain a lot of money/h killing them.