It's completely completed now It would've frozen before if there was no path directly to an enemy before, but now it will handle pathfinding in the following priority order:

• Find a path that will lead to a target.
• Find a path that will lead to a target if other characters were removed, and follow path until it hits a character.
• Find a path that will lead to a target if no collision is handled at all, and follow path until hits a wall.

This will handle any situation. Whether or not the enemy can actually reach a player character, it will get as close as possible. Below is an example screenshot of the fully completed AI.

The source code is both pasted here and attached. I commented pretty much every line, I hope that makes it at least a bit easier to understand.

.AI

.<DATA>

.Map buffer
det(768)→GDB0MB

.Map
[]→GDB0M
[000000010000000000010000]
[000000010000000000010000]
[000101010000000000010000]
[000000000000000101010101]
[000101010101010100000000]
[000100000000000000000000]
[000100000000000100000000]
[000000000000000100000000]

.Tiles
[]→GDB0T
[0000000000000000]
[FFFFFFFFFFFFFFFF]

.Target
[8142241818244281]→Pic0T
[8142241818244281]

.Character
[3C4281818181423C]→Pic0C
[3C7EFFFFFFFF7E3C]

.Ally data
.Number of characters
∆List(2ʳ)→GDB0A
.Data:
  .x position
  .y position
  .Max move distance
  .Other
  .data
  .you'll
  .probably
  .have
∆List(6,1,8,0,0,0,0,0)
∆List(1,0,8,0,0,0,0,0)

.Enemy data
.Number of enemies
∆List(3ʳ)→GDB0E
.Data:
∆List(10,6,8,0,0,0,0,0)
∆List(3,7,2,0,0,0,0,0)
∆List(11,2,8,0,0,0,0,0)


.<INITIALIZATION>

.Draw tilemap
GDB0M-1→D
0→Y
While -64
  0→X
  While -96
    Pt-Off(Y,X,{D+1→D}*8+GDB0T)→GDB0MB
    X+8→X
  End
  Y+8→Y
End

.Copy ally data to L₁
conj(GDB0A,L₁,258)

.Copy enemy data to L₁+258
conj(GDB0E,L₁+258,258)

Fix 5

.<MAIN LOOP>

Repeat getKey(15)

  .Advance AI if enter is pressed
  If getKey(9)
    .For each enemy
    For(r₁,1,{L₁+258}ʳ)
      .Let user know AI is thinking; T=test stage (0=normal, 1=ignore other enemies, 2=ignore walls)
      Text(0→T,,"THINKING...")
      .Update screen
      DispGraph
      .Pathfinding start
      Lbl PFS
      .ᴇ8000=Start of pathfinding map
      0→{ᴇ8000}ʳ
      .Fill pathfinding map with 0s
      Fill(ᴇ8001,254)
      .r₃=Iteration, r₂=pointer to enemy data; mark current location with 1
      1→r₃→{{r₁*8+L₁+258+2-8→r₂+1}*12+{r₂}+ᴇ8000}
      .Start of pathfinding loop
      Lbl PFL
      .Default to no viable path
      0→r₆
      .D=Data pointer in pathfinding map
      ᴇ8000→D
      .While data pointer is in the map
      While -ᴇ8000-96
        .If tile is not already part of a (shorter) path
        !If {D}
          .If tile can be traversed or in test stage 2
          If {D-ᴇ8000+GDB0M}=0+(T>1)
            .If tile borders the end of a path
            !If sub(PCL)
              .Check tile (skip pathfinding failed goto)
              Goto PFC
            End
            !If sub(PCR)
              Goto PFC
            End
            !If sub(PCD)
              Goto PFC
            End
            !If sub(PCU)
              Goto PFC
            End
            .Pathfinding failed
            Goto PFF
            .Pathfinding check
            Lbl PFC
            .If in test stage 0
            !If T
              .If tile is occupied by another character
              !If sub(PCC)
                .Pathfinding failed
                Goto PFF
              End
            End
            .For each allied character
            For(r₄,1,{L₁}ʳ)
              .If occupying current tile
              !If 0sub(O0)
                .Target found
                Goto PFE
              End
            End
            .Viable paths exist
            1→r₆
            .Mark as extension of path
            r₃+1→{D}
          End
        End
        .Pathfinding fail (tile cannot be traversed)
        Lbl PFF
        .Increase data pointer
        D+1→D
      End
      .Increase iteration
      r₃+1→r₃
      .If no viable path was found this iteration
      !If r₆
        .Increase test stage
        T+1→T
        .Reset pathfinding
        Goto PFS
      End
      .Continue pathfinding
      Goto PFL
      .Pathfinding end
      Lbl PFE
      .Length of path
      0→{ᴇ8060}ʳ
      .While not at start of path
      While r₃-1
        .If bordering tile is part of path
        !If sub(PCL)
          .Backtrack to tile
          Goto PFB
        End
        !If sub(PCR)
          Goto PFB
        End
        !If sub(PCU)
          Goto PFB
        End
        sub(PCD)
        .Pathfinding backtrack
        Lbl PFB
        r₄→D
        .Decrease iteration
        r₃-1→r₃
        .If distance to tile is not greater than maximum move distance
        !If >{r₂+2}
          .Record tile as part of path
          D-ᴇ8000→{{ᴇ8060}ʳ+1→{ᴇ8060}ʳ+ᴇ8062-1}
        End
        .If tile is occupied by another character
        !If sub(PCC)
          .Reset path
          Goto PFE
        End
        .If tile cannot be traversed
        If {D-ᴇ8000+GDB0M}
          .Reset path
          Goto PFE
        End
      End
      .For each element in path
      For(r₃,1,{ᴇ8060}ʳ)
        .Move character
        {{ᴇ8060}ʳ+ᴇ8062-r₃}→r₄^12→{r₂}
        r₄/12→{r₂+1}
        sub(D)
        Pause 256
      End
    End
    .Wait for user to let go of enter key
    While getKey(9)
    End
  End

  sub(D)
End


.<EXIT>

Fix 4
Return


.<SUBROUTINES>

.Draw everything
Lbl D
  .Draw map
  conj(GDB0MB,L₆,768)
  .Draw allies
  For(r₅,1,{L₁}ʳ)
    Plot1({r₅*8+L₁+2-8→r₆}*8,{r₆+1}*8,Pic0T)
  End
  .Draw enemies
  For(r₅,1,{L₁+258}ʳ)
    Plot1({r₅*8+L₁+258+2-8→r₆}*8,{r₆+1}*8,Pic0C)
  End
  .Update screen
  DispGraph
Return

.Pathfinding check tile
Lbl PCT
  {→r₄}-r₃
Return

.Pathfinding check left
Lbl PCL
  Dsub(O1) or (D-1sub(PCT))
Return

.Pathfinding check right
Lbl PCR
  D+1sub(O1) or (D+1sub(PCT))
Return

.Pathfinding check up
Lbl PCU
  D<ᴇ800C or (D-12sub(PCT))
Return

.Pathfinding check down
Lbl PCD
  ᴇ8053<D or (D+12sub(PCT))
Return

.Pathfinding check characters
Lbl PCC
  .For each enemy character
  For(r₄,1,{L₁+258}ʳ)
    .If occupying current tile
    !If 258sub(O0)
      .Tile cannot be traversed
       Goto PCF
    End
  End
  .Tile can be traversed
  1
  Return
  .Pathfinding check fail
  Lbl PCF
Return

.Optimization 0
Lbl O0
  {+(r₄*8)+1+L₁+2-8→r₅}*12+{r₅-1}+ᴇ8000-D
Return

.Optimization 1
Lbl O1
  -ᴇ8000^12=0
Return

Ah I see, so depending of different situations, the NPC will move differently?

Here is a screenshot I whipped up with lots of debug output. It's a great learning experience to watch how I did it. You can follow along with the screenshot with my explanation below.

AI 1 finds closest target, avoiding walls and other characters (stage 0), using flood fill method. AI 1 backtracks path by repeatedly finding a square with a value of 1 lower than the current square until reaching 1. Backtracking is recorded starting at 8 squares away (tile value 9, because the counting system is offset by one). AI 1 moves 8 tiles. AI 2 finds a path and backtracks it, but only moves 2 tiles. AI 3 cannot find a path to an enemy in stage 0 so... Change to stage 1, in which AI is allowed to make paths over other characters. This still fails, so... Change to the desperation stage 2, in which AI is allowed to make any path without collision. AI 3 knows it cannot reach a target, but gets as close to a target as possible. <END OF TURN> AI 1 cannot find a path, as the only route is blocked by another character. Change to stage 1, in which the path is allowed to cross over other characters. A target is found and backtracked, but... The path is reset where it hits the other character, so AI 1 doesn't walk right through AI 2. AI 1 follows the path that was reset to end at the other character. AI 2 and 3 move predictably. <FAST FORWARD> AI 1 cannot reach the target that is closer linearly because the path is blocked, so it keeps searching and finds a further target. AI 1 moves 8 squares towards its target. AI 2 moves next to a target. AI 3 fails. <END OF TURN> AI 1 finds a path of only 1 square to a target, so stops searching. AI 1 moves 1 square along that path of a possible 8 it could move. <EVERYBODY IS DONE>

---

@Aichi:



Give me a 20x20 map with multiple player and AI characters that I can test it on

EDIT: The algorithm scales easily to a 20x20 map. It may take upwards of 5 or 10 seconds for each AI character to make a move, but it works.

Wow, thanks! This is exactly that what I need.
Up to 10 seconds sounds kinda much (Btw: 10 Secs on 6Mhz, correct?), though. I will make sure I dont use too big maps with too many enemies. I cant test it for now, since I have to plan at first the development next days.

Edit: It seems to have trouble as an application and my game is going to be an app.

Can you post the program source for that so I can study it? Thanks!

I posted the source for people to look at on the first post of this page, here.

Wow, thanks! This is exactly that what I need.
Up to 10 seconds sounds kinda much (Btw: 10 Secs on 6Mhz, correct?), though. I will make sure I dont use too big maps with too many enemies. I cant test it for now, since I have to plan at first the development next days.

Edit: It seems to have trouble as an application and my game is going to be an app.

It uses a pretty slow flood filling algorithm currently that takes up most of the time, I'm sure I could optimize that to run a lot faster. As for incompatibility with apps, that's because I used 768 bytes of internal storage for the map buffer. This could be avoided by allocating a 768-byte appvar for the map buffer storage and storing the map there instead.

Oh, ok. Here it is, but it's horridly unoptimized because this is only for testing purposes and I just copied and pasted large sections of code around. I think the tilemap displaying code exists in three places now.

Press enter to start the AI's next turn, hold any key to fast forward.

To alter the map (currently only supports tiles being 0s or 1s), change the data stored into GDB0M. To change the player character data (what the AI targets, called "Ally data"), set the number of player characters appropriately in the ∆List(nʳ)→GDB0A line and then add 8 bytes of data for each character. Byte 1 = x position, byte 2 = y position, byte 3 = max move distance, and bytes 4-8 = unused, but fill in data here anyways. The AI character data is formatted exactly like the player character data, but is labeled "Enemy data" instead.

Wow.  This is very impressive.  Wonderful job Runer.