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

0 Members and 1 Guest are viewing this topic.

#### Runer112

• Project Author
• LV11 Super Veteran (Next: 3000)
• Posts: 2289
• Rating: +639/-31
##### 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 bufferdet(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 tilemapGDB0M-1→D0→YWhile -64  0→X  While -96    Pt-Off(Y,X,{D+1→D}*8+GDB0T)→GDB0MB    X+8→X  End  Y+8→YEnd.Copy ally data to L₁conj(GDB0A,L₁,258).Copy enemy data to L₁+258conj(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 4Return.<SUBROUTINES>.Draw everythingLbl 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  DispGraphReturn.Pathfinding check tileLbl PCT  {→r₄}-r₃Return.Pathfinding check leftLbl PCL  Dsub(O1) or (D-1sub(PCT))Return.Pathfinding check rightLbl PCR  D+1sub(O1) or (D+1sub(PCT))Return.Pathfinding check upLbl PCU  D<ᴇ800C or (D-12sub(PCT))Return.Pathfinding check downLbl PCD  ᴇ8053<D or (D+12sub(PCT))Return.Pathfinding check charactersLbl 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 PCFReturn.Optimization 0Lbl O0  {+(r₄*8)+1+L₁+2-8→r₅}*12+{r₅-1}+ᴇ8000-DReturn.Optimization 1Lbl O1  -ᴇ8000^12=0Return
« Last Edit: November 10, 2010, 11:49:33 pm by Runer112 »

#### Aichi

• Posts: 290
• Rating: +76/-3
##### 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 »

#### DJ Omnimaga

• Clacualters are teh gr33t
• CoT Emeritus
• LV15 Omnimagician (Next: --)
• Posts: 55942
• Rating: +3154/-232
• CodeWalrus founder & retired Omnimaga founder
##### 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)

#### AngelFish

• Is this my custom title?
• LV12 Extreme Poster (Next: 5000)
• Posts: 3242
• Rating: +270/-27
• I'm a Fishbot
##### 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²        ℏ²Ψ

#### Runer112

• Project Author
• LV11 Super Veteran (Next: 3000)
• Posts: 2289
• Rating: +639/-31
##### 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.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.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.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.

@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 »

#### DJ Omnimaga

• Clacualters are teh gr33t
• CoT Emeritus
• LV15 Omnimagician (Next: --)
• Posts: 55942
• Rating: +3154/-232
• CodeWalrus founder & retired Omnimaga founder
##### 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)

#### Aichi

• Posts: 290
• Rating: +76/-3
##### Re: Tilemap AI algorithm?
« Reply #21 on: November 11, 2010, 12:34:31 pm »
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.
« Last Edit: November 11, 2010, 02:13:14 pm by Aichi »

#### jnesselr

• King Graphmastur
• LV11 Super Veteran (Next: 3000)
• Posts: 2270
• Rating: +81/-20
• TAO == epic
##### 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!

#### Runer112

• Project Author
• LV11 Super Veteran (Next: 3000)
• Posts: 2289
• Rating: +639/-31
##### 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.
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.

#### jnesselr

• King Graphmastur
• LV11 Super Veteran (Next: 3000)
• Posts: 2270
• Rating: +81/-20
• TAO == epic
##### 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. ;-)

#### Runer112

• Project Author
• LV11 Super Veteran (Next: 3000)
• Posts: 2289
• Rating: +639/-31
##### 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 »

#### jnesselr

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

#### 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.
##### Re: Tilemap AI algorithm?
« Reply #27 on: November 11, 2010, 11:09:54 pm »
Wow.  This is very impressive.  Wonderful job Runer.
If I'm wrong, please correct me!
Unfinished Projects:
 Elmgon 14% Basic Movement Demo Homescreen Game Pack 80% Basic Latest Release Cube Droid Saves the Galaxy 65% Axe Demo Detonate 70% Axe
Completed Projects:
Exodus | Midnight |Drifter | Axe Snake | Jump! | Factory Theta | Spider | Plot Drop | Papi Jump | Numb3rs | Nibbler | Boost | Duel Tile Map Editor | Homescreen Map Editor | Key Group Check | Oasis