Author Topic: Tilemap AI algorithm?  (Read 13201 times)

0 Members and 1 Guest are viewing this topic.

Offline Runer112

  • Project Author
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: Tilemap AI algorithm?
« Reply #15 on: November 10, 2010, 11:34:15 pm »
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.

Code: [Select]
.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
« Last Edit: November 10, 2010, 11:49:33 pm by Runer112 »

Offline Aichi

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 290
  • Rating: +76/-3
    • View Profile
    • Devrays
Re: Tilemap AI algorithm?
« Reply #16 on: November 11, 2010, 12:37:36 am »
@ Runer
Thanks very much for this effort, Runer. I cant take a closer look on it, since I have to go to school now.
It seems to be very helpful. I just hope it handles path calculating on a 20x20 map fast enough.
Do you already implement target finding? I am looking for a target finding routine, that find the nearest green point.
But the important thing is not the distance. It are the fields that would be needed to reach the target,
so the enemy on the attached image should focus the dark green point, not the light green one.

@ Qwerty
It looks great, too. Hope you also post your source.

@ DJ Omnimaga
The map attached on the first post is not the only situation the AI has to solute.
In the real game the red point is elswhere, the green point too, and on different maps.

« Last Edit: November 11, 2010, 11:08:46 am by Aichi »

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55942
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: Tilemap AI algorithm?
« Reply #17 on: November 11, 2010, 12:38:23 am »
Ah I see, so depending of different situations, the NPC will move differently?
Now active at https://discord.gg/cuZcfcF (CodeWalrus server)

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: Tilemap AI algorithm?
« Reply #18 on: November 11, 2010, 01:17:33 am »
@ Qwerty
It looks great, too. Hope you also post your source.

It's working, but the target finding isn't quite as good as Runer's. I'd just go with his.
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline Runer112

  • Project Author
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: Tilemap AI algorithm?
« Reply #19 on: November 11, 2010, 01:27:12 am »
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.
« Last Edit: November 11, 2010, 02:05:18 am by Runer112 »

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55942
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: Tilemap AI algorithm?
« Reply #20 on: November 11, 2010, 01:36:58 am »
Woah! That's nice! I'll have to bookmark this post to read it later when I am feeling more sane to read lots of stuff. It seems like you made it as visual as possible, too, so I might be able to understand. :)

EDIT: Oh an edit. ^^
« Last Edit: November 11, 2010, 01:38:02 am by DJ Omnimaga »
Now active at https://discord.gg/cuZcfcF (CodeWalrus server)

Offline Aichi

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 290
  • Rating: +76/-3
    • View Profile
    • Devrays
Re: Tilemap AI algorithm?
« Reply #21 on: November 11, 2010, 12:34:31 pm »
Wow, thanks! This is exactly that what I need. :o
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.
« Last Edit: November 11, 2010, 02:13:14 pm by Aichi »

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: Tilemap AI algorithm?
« Reply #22 on: November 11, 2010, 07:06:49 pm »
Can you post the program source for that so I can study it? Thanks!

Offline Runer112

  • Project Author
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: Tilemap AI algorithm?
« Reply #23 on: November 11, 2010, 09:33:04 pm »
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. :o
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.

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: Tilemap AI algorithm?
« Reply #24 on: November 11, 2010, 09:40:03 pm »
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.
I meant one with the numbers. I think it would be better with the numbers to learn from. Plus it's cool to watch. ;-)

Offline Runer112

  • Project Author
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: Tilemap AI algorithm?
« Reply #25 on: November 11, 2010, 10:31:00 pm »
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.
« Last Edit: November 11, 2010, 10:32:56 pm by Runer112 »

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: Tilemap AI algorithm?
« Reply #26 on: November 11, 2010, 10:33:44 pm »
Thanks! I will try that out tomorrow.

Offline ztrumpet

  • The Rarely Active One
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5712
  • Rating: +364/-4
  • If you see this, send me a PM. Just for fun.
    • View Profile
Re: Tilemap AI algorithm?
« Reply #27 on: November 11, 2010, 11:09:54 pm »
Wow.  This is very impressive.  Wonderful job Runer. :)