SRL Archive - MSI Suggestions

I made this little route finder based on Dijkstra but this one is really slow. Takes seconds to find the path. But the main thing is that it really does find a short path. What makes it slow is the continuous PointInTPA, but I couldn't figure a way round that.

I think we could try to make this a bit faster and then use it in MSI. It will make adding new areas quite painful, but would allow us to easily handle the existing ones. It would find a route from anywhere to anywhere, thus allowing switching scripts. :)

How does it work:
the TPA you are inspecting as a map must be solid! No gaps, or it will not work!

1. Create a NodeArray from PointArray, which allows us to see which of the point's neighbors exist. Store info in booleans.
2. Start inspecting all neighbors of CurrentNode. If we haven't already been on neighbor X, take it into consideration.
3. Compare distances between the next node candidates (current's neighbors) and our goal point. Choose closest one as next node.
4. Repeat.

Test by running this on Simba:

program new;
{.include srl/srl.scar}
{.include srl/srl/misc/debug.scar}

const
  NORTH     = 0;
  EAST      = 1;
  SOUTH     = 2;
  WEST      = 3;
  NORTHEAST = 4;
  SOUTHEAST = 5;
  SOUTHWEST = 6;
  NORTHWEST = 7;


type
  Node = record
    X, Y: integer;
    N, E, S, W: boolean;
    NE, SE, SW, NW: boolean;
  end;

  NodeArray = array of Node;

function AnalyzeNodes(TPA: TPointArray): NodeArray;
var
  i, H: integer;
  P: TPoint;
begin
  H := High(TPA);
  SetLength(Result, H + 1);

  for i := 0 to H do
  begin
    // North
    P.X := TPA[i].X;
    P.Y := TPA[i].Y - 1;
    Result[i].X := P.X;
    Result[i].Y := P.Y;
    Result[i].N := PointInTPA(P, TPA);
    // East
    P.X := TPA[i].X +1;
    P.Y := TPA[i].Y;
    Result[i].X := P.X;
    Result[i].Y := P.Y;
    Result[i].E := PointInTPA(P, TPA);
    // South
    P.X := TPA[i].X;
    P.Y := TPA[i].Y + 1;
    Result[i].X := P.X;
    Result[i].Y := P.Y;
    Result[i].S := PointInTPA(P, TPA);
    // West
    P.X := TPA[i].X - 1;
    P.Y := TPA[i].Y;
    Result[i].X := P.X;
    Result[i].Y := P.Y;
    Result[i].W := PointInTPA(P, TPA);
    // North-East
    P.X := TPA[i].X + 1;
    P.Y := TPA[i].Y - 1;
    Result[i].X := P.X;
    Result[i].Y := P.Y;
    Result[i].NE := PointInTPA(P, TPA);
    // South-East
    P.X := TPA[i].X + 1;
    P.Y := TPA[i].Y + 1;
    Result[i].X := P.X;
    Result[i].Y := P.Y;
    Result[i].SE := PointInTPA(P, TPA);
    // South-West
    P.X := TPA[i].X - 1;
    P.Y := TPA[i].Y + 1;
    Result[i].X := P.X;
    Result[i].Y := P.Y;
    Result[i].SW := PointInTPA(P, TPA);
    // North-West
    P.X := TPA[i].X - 1;
    P.Y := TPA[i].Y - 1;
    Result[i].X := P.X;
    Result[i].Y := P.Y;
    Result[i].NW := PointInTPA(P, TPA);
  end;
end;

function PointToNode(P: TPoint; Nodes: NodeArray): Node;
var
  i, H: integer;
begin
  H := High(Nodes);
  for i := 0 to H do
    if (Nodes[i].X = P.X) and (Nodes[i].Y = P.Y) then
    begin
      Result := Nodes[i];
      Exit;
    end;
end;

function FindNodeInArray(X, Y: integer; Nodes: NodeArray): Node;
var
  i, H: integer;
begin
  H := High(Nodes);
  for i := 0 to H do
    if (Nodes[i].X = X) and (Nodes[i].Y = Y) then
    begin
      Result := Nodes[i];
      Exit;
    end;
  Result.X := -1;
  Result.Y := -1;
end;


function FindRoute(P1, P2: TPoint; TPA: TPointArray): TPointArray;
var
  Nodes: NodeArray;
  Visited: TPointArray;
  CurrentNode: Node;
  Finished: boolean;
  i, ii, tmpMIN, N: integer;
  Dists: array [0..7] of Integer;
begin
  Nodes := AnalyzeNodes(TPA);
  CurrentNode := PointToNode(P1, Nodes);
  SetLength(Result, 9999);
  SetLength(Visited, 9999);

  repeat
    Dists[NORTH]     := 9999999;
    Dists[EAST]      := 9999999;
    Dists[SOUTH]     := 9999999;
    Dists[WEST]      := 9999999;
    Dists[NORTHEAST] := 9999999;
    Dists[SOUTHEAST] := 9999999;
    Dists[SOUTHWEST] := 9999999;
    Dists[NORTHWEST] := 9999999;

    if CurrentNode.N then
      if not PointInTPA(Point(CurrentNode.X, CurrentNode.Y - 1), Visited) then
        Dists[NORTH] := Distance(CurrentNode.X, CurrentNode.Y - 1, P2.X, P2.Y);

    if CurrentNode.E then
      if not PointInTPA(Point(CurrentNode.X + 1, CurrentNode.Y), Visited) then
        Dists[EAST]  := Distance(CurrentNode.X + 1, CurrentNode.Y, P2.X, P2.Y);

    if CurrentNode.S then
      if not PointInTPA(Point(CurrentNode.X, CurrentNode.Y + 1), Visited) then
        Dists[SOUTH] := Distance(CurrentNode.X, CurrentNode.Y + 1, P2.X, P2.Y);

    if CurrentNode.W then
      if not PointInTPA(Point(CurrentNode.X - 1, CurrentNode.Y), Visited) then
        Dists[WEST]  := Distance(CurrentNode.X - 1, CurrentNode.Y, P2.X, P2.Y);

    if CurrentNode.NE then
      if not PointInTPA(Point(CurrentNode.X + 1, CurrentNode.Y - 1), Visited) then
        Dists[NORTHEAST] := Distance(CurrentNode.X + 1, CurrentNode.Y - 1, P2.X, P2.Y);

    if CurrentNode.SE then
      if not PointInTPA(Point(CurrentNode.X + 1, CurrentNode.Y + 1), Visited) then
        Dists[SOUTHEAST] := Distance(CurrentNode.X + 1, CurrentNode.Y + 1, P2.X, P2.Y);

    if CurrentNode.SW then
      if not PointInTPA(Point(CurrentNode.X - 1, CurrentNode.Y + 1), Visited) then
        Dists[SOUTHWEST] := Distance(CurrentNode.X + 1, CurrentNode.Y - 1, P2.X, P2.Y);

    if CurrentNode.NW then
      if not PointInTPA(Point(CurrentNode.X - 1, CurrentNode.Y - 1), Visited) then
        Dists[NORTHWEST] := Distance(CurrentNode.X - 1, CurrentNode.Y - 1, P2.X, P2.Y);

    tmpMIN := NORTH;
    for ii := EAST to NORTHWEST do
      if (Dists[ii] < Dists[tmpMIN]) then
        tmpMIN := ii;

    Visited[N] := Point(CurrentNode.X, CurrentNode.Y);

    case tmpMIN of
      NORTH : CurrentNode := FindNodeInArray(CurrentNode.X, CurrentNode.Y - 1, Nodes);
      EAST  : CurrentNode := FindNodeInArray(CurrentNode.X + 1, CurrentNode.Y, Nodes);
      SOUTH : CurrentNode := FindNodeInArray(CurrentNode.X, CurrentNode.Y + 1, Nodes);
      WEST  : CurrentNode := FindNodeInArray(CurrentNode.X - 1, CurrentNode.Y, Nodes);
      NORTHEAST: CurrentNode := FindNodeInArray(CurrentNode.X + 1, CurrentNode.Y - 1, Nodes);
      SOUTHEAST: CurrentNode := FindNodeInArray(CurrentNode.X + 1, CurrentNode.Y + 1, Nodes);
      SOUTHWEST: CurrentNode := FindNodeInArray(CurrentNode.X - 1, CurrentNode.Y + 1, Nodes);
      NORTHWEST: CurrentNode := FindNodeInArray(CurrentNode.X - 1, CurrentNode.Y - 1, Nodes);
    end;

    Result[N] := Point(CurrentNode.X, CurrentNode.Y);
    Inc(N);

    Finished := Dists[tmpMIN] <= 1;
    //WriteLn('Current='+ToStr(N)+', Dist='+ToStr(Dists[tmpMIN])+', tmpMIN='+ToStr(tmpMIN));
  until(Finished);

  SetLength(Result, N);
  ClearDoubleTPA(Result);
end;
////////////////////////////////////////////////////////////////////////////////
// THIS IS JUST FOR YOU TO TEST
var
  aTPA: array [0..1] of tpointarray;
  t, x, y, N: integer;
begin
  SetLength(aTPA[0], 9999);
  for x := 10 to 40 do
    for y := 15 to 40 do
    begin
      aTPA[0][N] := Point(x, y);
      Inc(N);
    end;
  for x := 41 to 70 do
    for y := 25 to 50 do
    begin
      aTPA[0][N] := point(x, y);
      Inc(N);
    end;
  for x := 71 to 100 do
    for y := 10 to 40 do
    begin
      aTPA[0][N] := point(x, y);
      Inc(N);
    end;
  SetLength(aTPA[0], N);
  //DebugTPA(aTPA[0], '');

  t := GetSystemTime;
  aTPA[1] := FindRoute(aTPA[0][0], aTPA[0][HIGH(aTPA[0])], aTPA[0]);
  t := GetSystemTime - t;
  WriteLn('Time : '+ToStr(t));
  DebugATPA(aTPA, '');
end.

EDIT: Hmm I think I try making is also work with NE, SE, SW, NW but I hope it doesn't make this way too slow.
EDIT: Done! Now checks all 8 neighbors. Will soon make a RS pathmaker.
EDIT: Dang… wasn't as easy as I thought…

34 Views, no comments? :(

Well, you're not the first one to make a Dijkstra implementation for SRL. :)

From: Wizzup?
Well, you're not the first one to make a Dijkstra implementation for SRL. :)

I haven't yet found a working one :S

It's interesting and if it works well yeah, it can be included in MSI. After all, we did mention MSI incorporating this sort of personal projects. :)

~RM

From: marpis

I think we could try to make this a bit faster and then use it in MSI. It will make adding new areas quite painful, but would allow us to easily handle the existing ones. It would find a route from anywhere to anywhere, thus allowing switching scripts. :)

Why would it be painful? If I understand correctly, it calculate's a path from one location to another. If in our TLocation record (not made yet) we have a TBox we can just calculate a path from the start location to the end location.

From: Coh3n
Why would it be painful? If I understand correctly, it calculate's a path from one location to another. If in our TLocation record (not made yet) we have a TBox we can just calculate a path from the start location to the end location.

Now recording the path takes 2 minutes depending on the length, this would need a solid path with no gaps. Making walkable TBoxes will take time. Unless we first set the bounds of the whole area we are in, and then record the bad areas we can't walk in and make a script that prints a TPA of the rest, that is walkable.

And also, making the walkable boxes connect eachother will take time. So that we could walk from anywhere to anywhere.

From: marpis
Now recording the path takes 2 minutes depending on the length, this would need a solid path with no gaps. Making walkable TBoxes will take time. Unless we first set the bounds of the whole area we are in, and then record the bad areas we can't walk in and make a script that prints a TPA of the rest, that is walkable.

And also, making the walkable boxes connect eachother will take time. So that we could walk from anywhere to anywhere.

That's not what I meant. I did this in a farming script I never finished (reflection broke). I'm talking about a TBox just for each location (LOC_VE_TREES, LOC_VE_BANK). What I did in my farming script was check to see if the player's tile was in that box, and therefore was in the correct location.

I meant that we could just pick a random point from each start loc and end loc box, then calculate the path.

with MSI_Locations[Which] do
begin
  // Other stuff here
  Bounds := IntToBox(Point(), Point(), Point(), Point());
end;

if (PointInBox(MyPos, MSI_Locations[].Bounds)) then
begin
  Writeln('We are in proper location');
  Path := GeneratePath(MyPos, EndLoc);
  WalkPath(Path);
end;

I have to say, using an A* algorithm might be bettter for something like this.

From: Nava2
I have to say, using an A* algorithm might be bettter for something like this.

A* Algorithm?

~RM

marpis your routefinder things looks crazy lol, but I do like what coh3n put up a little better. I mean its more simple, and not saying that simple is better, but that simple keeps things… simple ^^. great job none-the-less! thanks for taking the time to make something like that lol.

From: Rasta Magician
A* Algorithm?

~RM

A-star:

http://www.gamedev.net/reference/programming/features/astar/

Personally, I don't see how this could be properly implemented to work with colour RuneScape? It'll be pretty hard :/

[QUOTE=Dan's The Man;728382]A-star:

[url]http://www.gamedev.net/reference/programming/features/astar/[/url]

Personally, I don't see how this could be properly implemented to work with colour RuneScape? It'll be pretty hard :/

With reflection :p

From: Nava2
With reflection :p

Isn't reflection excluded from MSI due to its' constant downtime and project desertion?

Meh, well, it's not up to me to make decision on behalf of the MSI crew as I'm not even apart of it :/

[QUOTE=Dan's The Man;728407]Isn't reflection excluded from MSI due to its' constant downtime and project desertion?

Meh, well, it's not up to me to make decision on behalf of the MSI crew as I'm not even apart of it :/

Nope acctually the main half of the walking is reflection, if im correct? colour is backup.

From: BobboHobbo
Nope acctually the main half of the walking is reflection, if im correct? colour is backup.

Yup, color is backup :) Anyone who wants to write color walks is free to do it :)

~RM