.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
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.
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.
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.
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.
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.Re-read this and click the link. ;)
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 (http://www.youtube.com/watch?v=5PRABSTjLUw) (enemies are moving at 1:35).
.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
@ Qwerty
It looks great, too. Hope you also post your source.
(http://www.omnimaga.org/index.php?action=dlattach;topic=5251.0;attach=4392;image) |
|
Can you post the program source for that so I can study it? Thanks!
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.
I meant one with the numbers. I think it would be better with the numbers to learn from. Plus it's cool to watch. ;-)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 (http://ourl.ca/7848/139445).