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

0 Members and 1 Guest are viewing this topic.

Offline Aichi

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 290
  • Rating: +76/-3
    • View Profile
    • Devrays
Tilemap AI algorithm?
« on: November 10, 2010, 03:20:50 pm »
Hey Guys,
I have to provide for the NPC's AI - damn, how I hate this part of game developing. x.x
It should focus a location, then the NPC looks for a way to get there by differing free fields and blocked fields.
So I need a algorithm that is able to translate to axe (<2Kb) and that can reach the green point by starting on the red position in the attached image. Thanks in advance.

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 #1 on: November 10, 2010, 04:37:13 pm »
There are a lot of ways to do path planning algorithms. Do you want to have the path calculated on the fly (fast, but doesn't guarantee success) or precalculated (slow and you have to figure out where to store the path data)? Also, is there a known map that the algorithm can use? How important is it that the algorithm always finds the point? If it's very important that the point be found, then you're pretty much stuck with the potential fields approach. If it's not as important and the path will generally be fairly direct, then the simplest and fastest way is to give the character random motion with attraction to the point.

Given how complex the path is for that particular route, I'd recommend using potential fields with real time path plotting. Basically, you search out two or three "squares" from the current location and you weight the directional movement of the AI towards the point and away from walls, giving closer walls more negative weight than far walls. I'm not sure any simple algorithm is going to be able to find its way around that map, though. That doorway is really small and finding the point might necessarily involve complicated look-ahead routines.

I have an old routine around here that I developed for precisely this. I'll see if it will solve that.

EDIT: Here's the paper describing the method I used. I'm not sure if you can access it though.

A directional diffusion algorithm on cellular automata
for robot path-planning


Also, I apparently deleted the file. I'll rewrite it.
« Last Edit: November 10, 2010, 04:51:39 pm by Qwerty.55 »
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: Tilemap AI algorithm?
« Reply #2 on: November 10, 2010, 04:46:34 pm »
http://en.wikipedia.org/wiki/Pathfinding is a great article about pathfinding.  For a tilemap of that size, Dijkstra's algorithm is probably your best bet, although implementation can be a bit tricky.

Before i write up an algorithm, i have to ask, are there going to be more than one Red dot?  Is there only going to be a singleGreen dot?  Can the Green dot move?

ASHBAD_ALVIN

  • Guest
Re: Tilemap AI algorithm?
« Reply #3 on: November 10, 2010, 04:47:40 pm »
well, here's an easy way I discovered a long time ago and only costs you like 10-20 bytes of data storage:

You have a list of directions the an enemy/NCP is allowed to go, and run through them in sequential order.  Let's say the path takes 10 movements to get from point A to point B.  that's 10 list elements, each with a number specifying direction.  Let's take this code for ex.:
Code: [Select]
.PATH:
[01010303020303010101]->Str0
For(P,0,9)
.RIGHT
If {Str0+P}=1
X+1->X
End
.LEFT
If {Str0+P}=2
X-1->X
End
.UP
If {Str0+P}=3
Y-1->Y
End
.DOWN
If {Str0+P}=4
Y+1>Y
End
End
.End of subroutine, Interrupt, or just normal code section
.Continue on to rest of code or Return

You see, it'll read the path values, and if the value is equal to a certain number, the enemy will go that direction.

EDIT:
I realize now that this is not path based, it's more find the other dot based X.x
« Last Edit: November 10, 2010, 04:48:38 pm by ASHBAD_ALVIN »

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: Tilemap AI algorithm?
« Reply #4 on: November 10, 2010, 04:49:42 pm »
well, here's an easy way I discovered a long time ago and only costs you like 10-20 bytes of data storage:

You have a list of directions the an enemy/NCP is allowed to go, and run through them in sequential order.  Let's say the path takes 10 movements to get from point A to point B.  that's 10 list elements, each with a number specifying direction.  Let's take this code for ex.:
Code: [Select]
.PATH:
[01010303020303010101]->Str0
For(P,0,9)
.RIGHT
If {Str0+P}=1
X+1->X
End
.LEFT
If {Str0+P}=2
X-1->X
End
.UP
If {Str0+P}=3
Y-1->Y
End
.DOWN
If {Str0+P}=4
Y+1>Y
End
End
.End of subroutine, Interrupt, or just normal code section
.Continue on to rest of code or Return

You see, it'll read the path values, and if the value is equal to a certain number, the enemy will go that direction.

Isn't that more like following a specific path? Not actually finding the path itself?
« Last Edit: November 10, 2010, 04:50:16 pm by Builderboy »

ASHBAD_ALVIN

  • Guest
Re: Tilemap AI algorithm?
« Reply #5 on: November 10, 2010, 04:51:07 pm »
yeah I was thinking in terms of a tower defense game :P

Sorry for the interruption, proceed with discussion and ignore my suggestion.

Offline Aichi

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 290
  • Rating: +76/-3
    • View Profile
    • Devrays
Re: Tilemap AI algorithm?
« Reply #6 on: November 10, 2010, 05:54:03 pm »
There are a lot of ways to do path planning algorithms. Do you want to have the path calculated on the fly (fast, but doesn't guarantee success) or precalculated (slow and you have to figure out where to store the path data)?
I want to precalculate the path. I just hope that the speed is still nice on a 20x20 map with 15Mhz.

Also, is there a known map that the algorithm can use? How important is it that the algorithm always finds the point? If it's very important that the point be found, then you're pretty much stuck with the potential fields approach. If it's not as important and the path will generally be fairly direct, then the simplest and fastest way is to give the character random motion with attraction to the point.
The path should be exact as long as the calculating dont get too slow.
The page you link to is only for members that pay 20$ for a registration.

Before i write up an algorithm, i have to ask, are there going to be more than one Red dot?  Is there only going to be a singleGreen dot?  Can the Green dot move?
There will be many red dots in my game representing the enemies positions. A enemy is able to (just for example) walk 8 fields per round. If this enemy already doenst has a location to focus, he will search for one green point that he can reach with 8 fields. If there is no green point with this close, he will focus the next green point he can reach and keep this focus.
Now the enemy has a focus in any case, so a path from the enemy to the focused location will be precalculated and the enemy follow this path by 8 fields. In the next round the path has to be generated again, cause the green points (the players characters) are also able to move (the focus follow the character/green point automatically).
I dont know how feasable this is, since the tilemaps are going to be 20x20 and the focus searching routine & the path calculating routine must will repeat by up to 30 times per round. Also, I have to take a look on the needed memory size.
The result should be looks like this (enemies are moving at 1:35).

Offline Runer112

  • Project Author
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: Tilemap AI algorithm?
« Reply #7 on: November 10, 2010, 06:22:56 pm »
Well that certainly changes things... *throws away just about all the code I had been working on* :-\ I thought this would be like a real-time thing in which the enemy would track one moving target, like enemies tracking you in Zelda games. But now you mention that it's one of those turn-based games in which enemies have a maximum move distance and have to choose among multiple targets.

I suggest putting that in your first post so anyone else who wants to try it doesn't do the same thing I did and work for a while to find out later it isn't what you need.
« Last Edit: November 10, 2010, 06:41:04 pm by Runer112 »

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 #8 on: November 10, 2010, 07:35:32 pm »
There are a lot of ways to do path planning algorithms. Do you want to have the path calculated on the fly (fast, but doesn't guarantee success) or precalculated (slow and you have to figure out where to store the path data)?
I want to precalculate the path. I just hope that the speed is still nice on a 20x20 map with 15Mhz.

Also, is there a known map that the algorithm can use? How important is it that the algorithm always finds the point? If it's very important that the point be found, then you're pretty much stuck with the potential fields approach. If it's not as important and the path will generally be fairly direct, then the simplest and fastest way is to give the character random motion with attraction to the point.
The path should be exact as long as the calculating dont get too slow.
The page you link to is only for members that pay 20$ for a registration.

Okay. I have a hard copy of the file on my end, so I wasn't sure.

Precalculating is possible, but I'm not sure how it should be stored. The only efficient way I can think of would be to store a series of directional instructions, telling it Left, then Forward, then Forward, then Right, and so on. But that would mean you're wasting at least 1 byte for every tile moved and in all likelihood 2 bytes for a practical minimum (X and Y).

As for algorithms, the one I linked won't work. It's a real time system, as was the code I was working on.
« Last Edit: November 10, 2010, 07:38:15 pm by Qwerty.55 »
∂²Ψ    -(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 #9 on: November 10, 2010, 10:21:45 pm »
I win :)

The AI will find the shortest route to any opposing character, and then move as far along that route as possible (in this case, a maximum of 8 tiles). The AI will pull right up alongside the enemy, avoiding all walls and allied characters. It built it to be able to handle more than one AI character and more than one player character, I just haven't tried that yet.

The flashing "THINKING..." message when the AI is right next to the target is due to me repeatedly commanding the AI to make a move, but his move takes virtually no time to plan and execute.

EDIT: Yup, works flawlessly with more characters ;D . This is all automated. Observe the slower enemy on the left.
« Last Edit: November 10, 2010, 10:35:38 pm by Runer112 »

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 #10 on: November 10, 2010, 10:52:53 pm »
Nice!  Can we get the source for this? ;D

Offline Runer112

  • Project Author
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: Tilemap AI algorithm?
« Reply #11 on: November 10, 2010, 10:55:08 pm »
Sure, I just need to add some code to handle the case where there is no path to an enemy, I didn't add that yet.

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 #12 on: November 10, 2010, 11:00:04 pm »


Spoiler For Spoiler:
It's *technically* preprocessing  ;)

In all seriousness, I'm still working on it.
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55941
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: Tilemap AI algorithm?
« Reply #13 on: November 10, 2010, 11:02:39 pm »
I'M not sure if I missed anything, but why not just using a pre-stored path for the NPCs? ???  Like for example a NPC will go 2 steps right, 1 step up, stop one frame, move all the way back, stop again and so on? THere wouldn't be much need for AI, then, although he would stop moving while you're on his way.

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 #14 on: November 10, 2010, 11:05:29 pm »
There will be many red dots in my game representing the enemies positions. A enemy is able to (just for example) walk 8 fields per round. If this enemy already doenst has a location to focus, he will search for one green point that he can reach with 8 fields. If there is no green point with this close, he will focus the next green point he can reach and keep this focus.
Now the enemy has a focus in any case, so a path from the enemy to the focused location will be precalculated and the enemy follow this path by 8 fields. In the next round the path has to be generated again, cause the green points (the players characters) are also able to move (the focus follow the character/green point automatically).
I dont know how feasable this is, since the tilemaps are going to be 20x20 and the focus searching routine & the path calculating routine must will repeat by up to 30 times per round. Also, I have to take a look on the needed memory size.
The result should be looks like this (enemies are moving at 1:35).
Re-read this and click the link. ;)