Interesting, I remember re-coding in Cpp some quite speed-and-memory efficient kind of a shorter version of checkpoints backtracking (aka "smart bruteforcing") from Delphi (it was like some Warcraft2000 abandoned project), so my memory may not serve me right... It could 'cheat' -- shortcut the path and even had a chance to 'get lost' if checkpoints were only partially 'open' (known).
Well I tried to choose average distance... 12 tiles away in an area of 24x32 doesn't seem unreasonable... It was not about the constant, though - the point was that in case of BFS, it is quadratic, where as in case of A* it can be linear.
This is the reason A* is almost always the best choice for modern games.
However the situation is different for Spectrum games. They are limited to such a small playing area that, in this case, quadratic behavior is not a problem.
Also, I had an area with obstacles in my mind, rather than maze. In maze environments, search algorithms often degenerate to about the same case, so comparing them becomes nearly useless.
Good point. The level must have enough obstacles to require taking small detours (if it's too empty then there's no need for pathfinding), but it still has to be fairly open with many possible routes otherwise the "intelligent choices" in A* won't help.
It would be interesting to look at a practical example. I thought the most obvious example would be Pac-man, but when I simulated A* using this, it seems A* needed to process about half the map in many situations. I'm guessing a map size close to 24x32 is not big enough for A* to provide a significant difference. Here's an example:
In this case, even if my algorithm always processes all positions, each iteration only has to be 2 times faster than A* in order to achieve better results in worst cases. And I'm sure it would be a lot faster than this.
PS: I forgot to mention that simply processing all positions will work even better for this kind of game, because a single execution of my algorithm will be enough to find the shortest route for all 4 ghosts towards the player position!
Can you suggest other examples? It would be interesting to simulate them.
Perhaps you can try to modify your pseudocode example to see how little would have to be changed to turn it into A* to see that it would be worth it... :)
The pseudo-code change is trivial:
pathfind2(position SOURCE, position DESTINATION) {
create empty [strike]QUEUE[/strike] [B]WHATEVER[/B]
clear array DISTANCE[]
mark DISTANCE[DESTINATION] = 0
add DESTINATION to [strike]end of QUEUE[/strike] [B]WHATEVER[/B]
while [strike]queue[/strike] [B]WHATEVER[/B] is not empty
remove POSX from [strike]start of queue[/strike] [B]WHATEVER such that it's the position with minimum (distance from DESTINATION + estimated distance from SOURCE)[/B]
[B]if POSX is same as SOURCE then return "PATH FOUND"[/B]
for each [strike]unmarked[/strike] [B]unblocked[/B] position POSY, that is neighbor of POSX
[strike]if POSY is same as SOURCE then return "PATH FOUND"[/strike]
[strike]DISTANCE[POSY] = DISTANCE[POSX] + 1[/strike]
[B]distY = DISTANCE[POSX] + 1[/B]
[B]if POXY is unmarked or DISTANCE[POSY] > distY[/B]
[B]DISTANCE[POSY] = distY[/B]
[B]calculate estimated distance from SOURCE[/B]
[B]if POSY is already inside WHATEVER
move POSY inside WHATEVER
else[/B]
add POSY to [strike]end of QUEUE[/strike] [B]WHATEVER[/B]
return "THERE'S NO PATH"
}
The problem is, the extra Z80 assembly code required to manage whatever data structure you choose (that supports repeatedly inserting elements and extracting current minimum element according to calculated heuristics) will make the implementation above several times slower than the original pseudo-code.
Array A[] which points to first element on double linked list of nodes. All nodes on a list at A[c] have the same total (estimated) cost to destination equal to c.
OK, I agree this "bucket sort" data structure is a very good choice for A*. Even so, I still believe it's not worth it.
The problem is, you are applying asymptotic analysis to a limited size problem (i.e levels limited to size 24x32). Therefore the value of these constants make all the difference.
For comparison, my algorithm only requires a single circular buffer. The best implementation would use a 256-aligned area of 256 bytes, with register HL pointing to first element and DE to next available position.
Here's the entire code to add an element to end of queue:
LD (DE), A
INC E
The entire code to remove an element from start of queue:
LD A, (HL)
INC L
The entire code to calculate queue size (or check if it's empty):
LD A, E
SUB L
And the entire code to create queue and already add the first DESTINATION element:
LD HL, queue
LD (HL), A
LD DE, queue+1
Even if the actual algorithm implementation requires using IX/IY instead of HL/DE, or storing 2 bytes instead of 1, it won't be much different than this. In a Spectrum game, this should be fast enough to always process all level positions in a single frame.
I'm sure that implementing the data structure you proposed would be several times slower than this, Therefore, whenever A* requires processing a significant percentage of the map (such as the example in my previous post), it could take a very long time to finish.
Just wanted to say a thankyou there Einar Saukas for your circular buffer code there... You just made another abstract concept look extremely comprehensible to a beginner like me!... Ill definitely be putting that code aside somewhere for future use!!!
Just wanted to say a thankyou there Einar Saukas for your circular buffer code there... You just made another abstract concept look extremely comprehensible to a beginner like me!... Ill definitely be putting that code aside somewhere for future use!!!
The problem is, you are applying asymptotic analysis to a limited size problem (i.e levels limited to size 24x32). Therefore the value of these constants make all the difference.
Not at all. The size of the level plays no role in the analysis. Perhaps you should re-read that...
Here's the entire code to add an element to end of queue:
LD (DE), A
INC E
Do you suggest that your implementation can't deal with paths longer than 255 bytes? Or how exactly do you encode one of the 768 nodes into 8 bits?
Edit: Ah, I noticed you mentioning the two bytes. Makes me wonder why claim it can be implemented like this when it can't...
Anyway, I am getting kind of tired of this debate. I just wanted to provide hints about A* to anyone interested, not to argue about your preferred algorithm...
However the situation is different for Spectrum games. They are limited to such a small playing area that, in this case, quadratic behavior is not a problem.
Well, 24*24 vs 3*12 still looks like big difference to me, even for the trivial example I gave...
It would be interesting to look at a practical example. I thought the most obvious example would be Pac-man, but when I simulated A* using this, it seems A* needed to process about half the map in many situations. I'm guessing a map size close to 24x32 is not big enough for A* to provide a significant difference.
Nice visualiser, BTW. The reason why A* shows little advantage is because the area is a maze like, so each algorithm works basically the same as I mentioned before. The only difference you can get are the additional optimizations like jumping to corners along direct lines etc. to limit the amount of nodes inserted, not the search as such.
Try to apply it to something like this or this or any other CCS war game and you will see how much does BFS/Dijkstra suck...
The problem is, the extra Z80 assembly code required to manage whatever data structure you choose (that supports repeatedly inserting elements and extracting current minimum element according to calculated heuristics) will make the implementation above several times slower than the original pseudo-code.
That's just an unprooven claim. Might be true, might be not. I am not going to waste my life trying, though. Perhaps Bob Smith might tell us how fast he was able to implement it...
The problem is, you are applying asymptotic analysis to a limited size problem (i.e levels limited to size 24x32). Therefore the value of these constants make all the difference.
Not at all. The size of the level plays no role in the analysis. Perhaps you should re-read that...
You misunderstood me.
Of course asymptotic analysis doesn't depend on level size, and that's the most important characteristic of any algorithm to solve problems with arbitrary size. However Spectrum maps don't have arbitrary size. They are limited to a maximum size of 24x32.
For instance, if we have an algorithm that solves a certain problem in time N*N, and another that solves it in time 10*N*log2(N), according to asymptotic analysis the second option is obviously much better as a general solution. However, if you are going to implement it in a machine where always N<=32, then the first option becomes a better choice in this case.
This is the reason I said that maximum Spectrum level sizes are so small that the constants make all the difference.
Do you suggest that your implementation can't deal with paths longer than 255 bytes?
No. I just suggested that it's never necessary to store more than a hundred "pending neighbors" in the queue at the same time, thus a circular buffer of 256 bytes will be large enough.
Or how exactly do you encode one of the 768 nodes into 8 bits?
In my Pac-man example, notice there's no need to consider every single character as a valid position. It would be enough to only take into account positions at the relevant rows/columns, as follows:
This way, the algorithm can process it like a 10x12 map. This way, a single byte would be enough to store each coordinate, and processing will be a lot faster. The result won't be exact since a few passages are slightly longer than others, but I doubt the player would notice the difference.
However, in games where this kind of simplification doesn't apply, I agree it's necessary to store 2 bytes instead of 1 for each queue position. That's something I mentioned in my previous post.
Anyway, I am getting kind of tired of this debate. I just wanted to provide hints about A* to anyone interested, not to argue about your preferred algorithm...
I though this was an interesting technical discussion. I agree it doesn't make sense to turn this into an argument!
Nice visualiser, BTW. The reason why A* shows little advantage is because the area is a maze like, so each algorithm works basically the same as I mentioned before. The only difference you can get are the additional optimizations like jumping to corners along direct lines etc. to limit the amount of nodes inserted, not the search as such.
I suspected A* didn't have enough advantage because the map wasn't large enough, despite providing multiple paths. But I really don't know. Can you suggest a 24x32 map that would be a better example?
Try to apply it to something like this or this or any other CCS war game and you will see how much does BFS/Dijkstra suck...
If we consider any individual screen from these games, A* doesn't seem favorable either.
But do you mean finding a path across the entire game (i.e. for enemies moving through several screens)? If so, A* would be clearly the best choice. All my previous comments only apply to maps up to 24x32. However, are you sure any of these games really have multi-screen pathfinding? It's really surprising that any Spectrum game can afford to dedicate enough memory and processing time to do that.
If we consider any individual screen from these games, A* doesn't seem favorable either.
Really? I don't get how you can come to such conclusion. The latter ones are typical examples of a grid with variable terrain costs, with few impassable areas (depending on the unit type). A* should ace Dijkstra in such environment with ease...
It would be very interesting to have an optimized A* library for the Spectrum. Too bad this won't happen! :(
Why don't you take on the challenge yourself, then? :)
Regarding the "simplified Dijkstra" algorithm I posted above, notice it also works for different types of terrain. For instance, an unmarked position next to value "3" should be usually marked with value "4", but if it's forest terrain you can mark it with "5" instead (since it will take twice as long to travel to its neighbor), or if it's mountain terrain you can mark it with "6" instead, and so on....
BTW, this wouldn't work unless you would change how you choose the next node to process and include reevaluating of node's cost when processing neighbors. Otherwise your algorithm might fail to find the shortest path...
A* is very doable on the spectrum - I've done it myself though never tested. There are variations you can read about (or figure out yourself) that attempt to stay in memory limits too. If you need asm data structures, there are a few in z88dk's code repository and perhaps more on my hard drive. I used a heap data structure for my A* implementation.
You may not need A* if your map is static and number of goals are small. Look up the "smelly algorithm" (IIRC) that can let you store best direction for each position in the map. The idea is simple: the goal position emits a stink of strength zero that grows by 1 for each step taken from the goal. You can traverse the map from the goal and store the stink at each map position before the gameplay begins so that the map stores best direction to the goal (decrease stink by 1) for every map position.
Sorry if this has been mentioned before, I don't have much time for Sinclair stuff these days,.
The latter ones are typical examples of a grid with variable terrain costs, with few impassable areas (depending on the unit type). A* should ace Dijkstra in such environment with ease...
Different terrain types (i.e. pathfinding with "weighted" positions) is a different matter... see below.
Regarding the "simplified Dijkstra" algorithm I posted above, notice it also works for different types of terrain. For instance, an unmarked position next to value "3" should be usually marked with value "4", but if it's forest terrain you can mark it with "5" instead (since it will take twice as long to travel to its neighbor), or if it's mountain terrain you can mark it with "6" instead, and so on...
BTW, this wouldn't work unless you would change how you choose the next node to process and include reevaluating of node's cost when processing neighbors. Otherwise your algorithm might fail to find the shortest path...
No, there's no need to reevaluate costs. In this case, the idea remains exactly the same as I wrote in #21: first process all positions that are 1 step away from the goal, then all positions 2 steps away from the goal, then 3, etc.
In the example above, if you are processing all positions 3 steps away from the goal, and you find a mountain neighbor, then it should be marked as "6" instead of "4". Afterwards, the mountain neighbor will have to wait longer than other neighbors, until it's turn "6". And that's perfectly fine!
I previously provided in #27 a detailed explanation for the most efficient implementation for regular maps. Now I will provide a similar explanation for maps with irregular terrain. But first, let me explain the data structure we will need.
Let's consider we have 3 types of terrain, as I mentioned above: "path" that takes 1 step to move, "forest" that takes 2 steps, and "mountain" that takes 3 steps. In this case, instead of 1 queue, this implementation will require 4 stacks. Notice that stacks are more efficient than queues, since they can be located anywhere (there's no need for boundary alignment or anything), and we only need a register per stack storing the address of its first element (we can simply put $ff at the bottom to mark the end of each stack, so it's easy to check if it's empty without using another register or even remembering its initial address).
These 4 stacks will be called STACK[0], STACK[1], STACK[2] and STACK[3]. They will initially store positions that are 0, 1, 2, or 3 steps away. In practice, it means STACK[0] will contain the positions that we are currently processing, we will put their "path" neighbors in STACK[1], their "forest" neighbors in STACK[2], and their "mountain" neighbors in STACK[3].
After we finish processing all positions from STACK[0], then all stacks addresses are "rotated", such that STACK[1] becomes STACK[0], STACK[2] becomes STACK[1], STACK[3] becomes STACK[2], and finally STACK[0] (now empty) becomes STACK[3]. Then we repeat the process. This way, we will be now processing all positions 1 step further away from the goal, without the need to recalculate anything.
Here's the pseudo-code for this implementation:
pathfind(position SOURCE, position DESTINATION) {
create empty stacks
clear array DISTANCE[]
mark DISTANCE[DESTINATION] = 0
add DESTINATION to top of STACK[0]
repeat
while STACK[0] is not empty
remove POSX from top of STACK[0]
for each unmarked position POSY, that is neighbor of POSX
if POSY is same as DESTINATION then return "PATH FOUND"
n = TERRAIN[POSY]
DISTANCE[POSY] = DISTANCE[POSX] + n
add POSY to top of STACK[n]
rotate stack addresses
until all stacks are empty
return "THERE'S NO PATH"
}
Of course this implementation will be somewhat slower than #27 since it requires a few extra operations, but probably not much. And each iteration of this algorithm should be still much faster than each iteration of A*.
Which solution works better? It depends on how many positions A* will need to process. If A* processes only a few positions, then A* will certainly finish faster. However if A* needs to process a significant percentage of the map, then the faster iterations in my algorithm above should help it finish faster, even if it has to process all map positions (assuming a Spectrum level size limited to 24x32 as usual).
The problem with A* is, I suspect the analyzed area in A* will be even larger in an irregular terrain. Whenever A* finds a forest area or a small mountain, the analyzed path will naturally start expanding sideways, so A* will try multiple routes crossing the mountain and also attempting to walk around it. If it was a very large map, then it would not matter that A* was processing a long path that is a few positions wide, because this path would still represent a very small percentage of the total area. However, if the map is only 24x32, then a path a few positions wide would cover most of the map! Anyway too bad I could not find an online simulator for this situation, it would be fun to watch this working.
Finally there's another advantage for using my algorithm instead of A* in this situation: irregular terrains are typical of strategy war games. These games always have multiple troops at different locations. Since my algorithm can mark distance from goal for every map position, a single execution will be enough to find the shortest path for each enemy soldier towards a player position. Even better: if the player also has multiple soldiers at different positions, my algorithm can be executed for multiple destinations. You would just need to initialize STACK[0] with all these destinations. This way, a single execution would be enough to determine, for each enemy position, the shortest path to its closest player soldier! This would not work in A*.
You may not need A* if your map is static and number of goals are small. Look up the "smelly algorithm" (IIRC) that can let you store best direction for each position in the map. The idea is simple: the goal position emits a stink of strength zero that grows by 1 for each step taken from the goal. You can traverse the map from the goal and store the stink at each map position before the gameplay begins so that the map stores best direction to the goal (decrease stink by 1) for every map position.
OK, that's pretty much how the algorithm I described works. :)
The implementation details (intended for Z80 assembly) were presented in #21, #27 and #34 if you are interested.
No, there's no need to reevaluate costs. In this case, the idea remains exactly the same as I wrote in #21: first process all positions that are 1 step away from the goal, then all positions 2 steps away from the goal, then 3, etc.
In the example above, if you are processing all positions 3 steps away from the goal, and you find a mountain neighbor, then it should be marked as "6" instead of "4". Afterwards, the mountain neighbor will have to wait longer than other neighbors, until it's turn "6". And that's perfectly fine!
I see - so you consider it 6 steps away, even if it is 4 steps away.
In that case what you are describing is no different than the A* I have described above - your 4 stacks is the sliding window of the bucket sort like array I mentioned. Ergo the implementation can be entirely the same, except that you don't add the heuristics which guides you towards the goal into the mix, and thus have to needlessly process much more nodes. Seems like pretty obvious loss to me.
Finally there's another advantage for using my algorithm instead of A* in this situation: irregular terrains are typical of strategy war games. These games always have multiple troops at different locations. Since my algorithm can mark distance from goal for every map position, a single execution will be enough to find the shortest path for each enemy soldier towards a player position. Even better: if the player also has multiple soldiers at different positions, my algorithm can be executed for multiple destinations. You would just need to initialize STACK[0] with all these destinations. This way, a single execution would be enough to determine, for each enemy position, the shortest path to its closest player soldier! This would not work in A*.
Two points:
- why should all units in a strategy game head toward single point?
- you can use A* to find multiple paths at the same time as well. Just swap start and destination and use multiple starting points.
Welcome back Alcoholic Anonymous! Please tell me what should I do with the Abbaye project.
As you know I've finished all the background stuff for the rooms. At the moment another coder is working on a new code for the game, but from scratch. If you tell me how, I can continue with your code, putting the enemies/ collisions/events.
If not, I hope that the coder will finish the project.
Is everything ok?
Write back soon,
D.H.
In that case what you are describing is no different than the A* I have described above - your 4 stacks is the sliding window of the bucket sort like array I mentioned. Ergo the implementation can be entirely the same, except that you don't add the heuristics which guides you towards the goal into the mix, and thus have to needlessly process much more nodes. Seems like pretty obvious loss to me.
Not really. There's a lot more work involved in A*. Here's a list:
In algorithm #44, calculation of POSY cost is very simple: "POSX.dist + terrain". In A*, it's also required to calculate and add estimated distance to source. If Manhattan distance it's "POSX.dist + terrain + abs(POSY.row-SOURCE.row)+abs(POSY.col-SOURCE.col)". If Chebyshev distance it's "POSX.dist + terrain + max(abs(POSY.row-SOURCE.row),abs(POSY.col-SOURCE.col))". If Euclidean distance it's "POSX.dist + terrain + lookup(abs(POSY.row-SOURCE.row),abs(POSY.col-SOURCE.col))". Any of these additional calculations take some time in Z80 assembly.
In algorithm #44, each position is calculated, marked, added to the queue, later removed and processed only once. In A*, this may happen with the same position several times (when it's visited from north, from south, from east, and again from west). The problem is, positions are not visited in order of increasing distance in A*. Because of this, visiting the same position again from another direction may provide a shorter path, so this position always have to be recalculated, then it may also need to be marked, added to the queue, later removed and processed all over again.
Implementing algorithm #44 using stacks will work just fine. But implementing A* this way has an additional problem: whenever you revisit a position from a different direction and obtain a different value from multiple recalculations, you also need to check if this position is already inside any of the existing queues. If so, you need to remove it from inside this queue, before adding it to the top of another queue. An efficient implementation will require an additional memory area of 24*32*2=1536 bytes containing the address of each position inside the queues, also spend some time to update this area whenever a position is added or removed from a queue, and the extra time required for the logic to remove a position from the middle of a queue.
Since I mentioned memory, that's another relevant issue. Algorithm #44 requires 4 stacks with about 100 slots each, thus using a temporary area of 4*100*2=800 bytes. The explanation for 100 slots is simple. The worst case for this algorithm is a 24x32 map that contains only path terrain, with a target at the center. How many positions are exactly 15 steps away? Exactly 24 (one per column) on each side, thus a total of 48. Now using 3 different kinds of terrain (path, forest, mountain) you will be able to create a few more areas closer to the target that will require the same number of steps to reach, but not too many. Thus twice the original number is a safe bet. Now let's consider A*. Now the worst case is a 24x32 map that contains only path terrain, with the target at the top left corner, and source at lower right corner. According to A* calculation, the top left position has distance zero from target and estimated distance 23+31=54 to source, thus a total cost of 54. The problem is, every position in the entire map also have exactly the same total cost of 54, because whenever you increase distance from target you also decrease estimated distance to source. Therefore nothing prevents A* from visiting all positions and adding all of them to the same stack. Thus the maximum size for each stack is about 32*24*2=1536. Also you will need 5 stacks instead of 4. Therefore the total temporary area for A* in a 24x32 map (including address of each position inside the queues as mentioned above) should be 5*1536+1536=9216 bytes. That's a lot. Unless you use a more flexible data structure to save memory (such as the double linked list you mentioned before), but in this case it will take a lot more processing time to manage it. Anyway the worst case I mentioned for A* can be easily simulated here:
In best cases, A* may process very few positions and save a lot of time. In worst cases, A* may process almost all positions in a 24x32 map, process many of these position more than once, and spend more time on each iteration (also using a lot more memory), thus the total time may be much longer than algorithm #44. For a Spectrum game, is it better to use an algorithm that always take 1 frame to find all paths, or an algorithm that will sometimes take only 10% of a frame, but sometimes spend 3 or 4 frames? I think it's the former.
As I mentioned before, A* is very effective in large maps. But in a 24x32 map, the extra effort is not worth it, because the map is so small that every little detour will make it cover a large percentage of the map anyway. There are actually some good animations demonstrating it in Wikipedia. Here's the animation for Dijkstra's algorithm (that works just like mine in this case):
Now here's the animation for A*:
Notice that the first search advances in all directions. This would be really bad if you imagine this scene as just a very tiny "zoomed in" part from a giant map. In comparison, A* is considerably smarter and moves towards the goal, which would work much better as part of a giant map... However, now imagine both scenes are already showing the entire map. In this case, the first search visited about 95% of the entire map, and A* visited "only" about 65%. Considering that each iteration of A* is slower and it uses a lot more memory, if it has to visit most positions anyway it means A* is not worth it in small maps!
Finally, notice that A* implementation is only "comparable" to algorithm #44 in variable terrain, using a single source and single target. Even so, there should be a significant difference in performance for each iteration due to the reasons I listed above. The problem is, variable terrain is typically used in strategy war games, that don't usually have a single source and/or single target... In a single type of terrain, algorithm #44 is even faster. Or when processing multiple sources and/or multiple targets, A* doesn't work so well either. See below.
- why should all units in a strategy game head toward single point?
In a Dune-based RTS, you could activate a thumper device to temporarily attract all sandworms towards this single location, ignoring all human troops for some time...
But I agree with you here. Strategy games typically require multiple sources and targets. This is another advantage of algorithm #44 since processing time is essentially the same regardless of how many sources and targets, unlike A*.
- you can use A* to find multiple paths at the same time as well. Just swap start and destination and use multiple starting points.
Not really.
If you start search from multiple locations towards a single goal, each one of them will usually start with different costs, thus using 5 stacks won't be enough. Therefore you will need much more than 9K as temporary memory, or use a slower, more complex data structure.
The alternative (search from a single location towards multiple goals) [strike]won't work because this won't give a consistent heuristic[/strike]. EDIT: Ops! I just realized I was wrong about this. The same heuristics should be valid. The problems in this alternative are different. If you use A* to search towards multiple locations, it will only find the route to the closest one, instead of providing solutions for all of them in a single execution. It will also require even more processing, since every iteration will need to calculate estimated distance to all goals to compare them. Another problem is that multiple goals should drive A* search towards multiple directions, thus ruining the main advantage of A* (i.e. directing the search only towards the goal instead of moving towards all directions).
However strategy games typically require multiple sources and multiple targets. The computer troops usually choose a few important targets, then move each attack unit towards its closest target. I can't see an efficient way to implement multiple sources and multiple targets in a Spectrum game using A*...
Although pathfinding is a very interesting theme, I'm afraid this discussion is getting boring. I suggest we shift the focus of this thread in a more productive direction...
Therefore I have implemented the "simplified Dijkstra" algorithm from post #27:
1 REM SINGLE PATHFINDER DEMO
2 REM by Einar Saukas * 2013
3 REM
10 BORDER 0: CLEAR 59999
20 RANDOMIZE : RESTORE : FOR f=USR "a" TO USR "c"+7: READ z: POKE f,z: NEXT f
30 FOR f=1 TO 704: LET z=RND>.3: PRINT PAPER 2+5*z;CHR$ 144;: NEXT f
40 INPUT "Source row (1-22)? ";sx: INPUT "Source col (1-32)? ";sy
50 INPUT "Target row (1-22)? ";tx: INPUT "Target col (1-32)? ";ty
60 PRINT PAPER 4;AT sx-1,sy-1;CHR$ 145;AT tx-1,ty-1;CHR$ 146
70 DIM d(22,32): LET d(tx,ty)=2
80 LET q1=60000: LET q2=60000
90 LET px=tx: LET py=ty
100 PRINT AT px-1,py-1; PAPER 5; OVER 1;" "
110 IF px>1 THEN IF NOT d(px-1,py) THEN LET nx=px-1: LET ny=py: GO SUB 200
120 IF px<22 THEN IF NOT d(px+1,py) THEN LET nx=px+1: LET ny=py: GO SUB 200
130 IF py>1 THEN IF NOT d(px,py-1) THEN LET nx=px: LET ny=py-1: GO SUB 200
140 IF py<32 THEN IF NOT d(px,py+1) THEN LET nx=px: LET ny=py+1: GO SUB 200
150 IF q1<q2 THEN LET px=PEEK q1: LET py=PEEK (q1+1): LET q1=q1+2: GO TO 100
160 PRINT #0;AT 1,9; FLASH 1;" NO SOLUTION! ": STOP
200 IF ATTR (nx-1,ny-1)>31 THEN LET d(nx,ny)=d(px,py)+1: POKE q2,nx: POKE q2+1,ny: LET q2=q2+2: PRINT AT nx-1,ny-1; PAPER 6; OVER 1;" "
210 IF nx<>sx OR ny<>sy THEN RETURN
220 PRINT #0;AT 1,8; FLASH 1;" SOLUTION FOUND "
230 LET px=sx: LET py=sy
240 PRINT AT px-1,py-1; PAPER 4; OVER 1;" ": LET z=d(px,py)-1
250 IF px>1 THEN IF d(px-1,py)=z THEN LET px=px-1: GO TO 240
260 IF px<22 THEN IF d(px+1,py)=z THEN LET px=px+1: GO TO 240
270 IF py>1 THEN IF d(px,py-1)=z THEN LET py=py-1: GO TO 240
280 IF py<32 THEN IF d(px,py+1)=z THEN LET py=py+1: GO TO 240
290 DATA 128,z,z,z,z,z,z,255,128,190,160,190,130,190,128,255,z,193,247,z,z,z,255,z
This is just a simple implementation in BASIC, therefore too slow for practical use. I will rewrite it in assembly later... Even so, this BASIC version is quite useful as a demo, so people can see how it works in practice, and it should be easier to understand the source code.
When you run this program, it will generate a random map like this:
At this point, if you are not happy with the generated map, you can simply export the screen from the emulator, edit it in ZX-Paintbrush, and import again. You don't even need to use the same colors: every char position with a dark PAPER (colors 0,1,2,3 without BRIGHT) are interpreted as obstacles, everything else as paths.
Afterwards you must choose a single source and target, then you will see the pathfinder in action. During execution, neighbor positions stored in the queue are marked in yellow, and already processed positions are marked in cyan. If the map has a valid solution, the program execution will finish like this:
You can download the TZX version of this program here.
Somehow I suspect nobody's interested on pathfinding anymore :)
Even so, I made a small change to previous implementation so it now supports multiple sources and multiple targets. In practice, it only means that this variant will calculate paths for the entire map, without bothering to check the source positions at every step:
1 REM MULTI PATHFINDER DEMO
2 REM by Einar Saukas * 2013
3 REM
10 BORDER 0: CLEAR 59999
20 RANDOMIZE : RESTORE : FOR f=USR "a" TO USR "c"+7: READ z: POKE f,z: NEXT f
30 FOR f=1 TO 704: LET z=RND>.3: PRINT PAPER 2+5*z;CHR$ 144;: NEXT f
40 DIM d(22,32): LET q1=60000: LET q2=60000
50 INPUT "Sources? ";s: DIM a(s): DIM b(s): FOR f=1 TO s: INPUT "Source ";(f);" row (1-22)? ";a(f): INPUT "Source ";(f);" col (1-32)? ";b(f): PRINT PAPER 4;AT a(f)-1,b(f)-1;CHR$ 145: NEXT f
60 INPUT "Targets? ";t: DIM i(t): DIM j(t): FOR f=1 TO t: INPUT "Target ";(f);" row (1-22)? ";i(f): INPUT "Target ";(f);" col (1-32)? ";j(f): PRINT PAPER 4;AT i(f)-1,j(f)-1;CHR$ 146: LET d(i(f),j(f))=2: POKE q2,i(f): POKE q2+1,j(f): LET q2=q2+2: NEXT f
70 LET px=PEEK q1: LET py=PEEK (q1+1): LET q1=q1+2: PRINT AT px-1,py-1; PAPER 5; OVER 1;" "
80 IF px>1 THEN IF NOT d(px-1,py) THEN LET nx=px-1: LET ny=py: GO SUB 200
90 IF px<22 THEN IF NOT d(px+1,py) THEN LET nx=px+1: LET ny=py: GO SUB 200
100 IF py>1 THEN IF NOT d(px,py-1) THEN LET nx=px: LET ny=py-1: GO SUB 200
110 IF py<32 THEN IF NOT d(px,py+1) THEN LET nx=px: LET ny=py+1: GO SUB 200
120 IF q1<q2 THEN GO TO 70
130 FOR f=1 TO s: LET px=a(f): LET py=b(f)
140 PRINT AT px-1,py-1; PAPER 4; OVER 1;" ": LET z=d(px,py)-1
150 IF px>1 THEN IF d(px-1,py)=z THEN LET px=px-1: GO TO 140
160 IF px<22 THEN IF d(px+1,py)=z THEN LET px=px+1: GO TO 140
170 IF py>1 THEN IF d(px,py-1)=z THEN LET py=py-1: GO TO 140
180 IF py<32 THEN IF d(px,py+1)=z THEN LET py=py+1: GO TO 140
190 NEXT f: STOP
200 IF ATTR (nx-1,ny-1)>31 THEN LET d(nx,ny)=d(px,py)+1: POKE q2,nx: POKE q2+1,ny: LET q2=q2+2: PRINT AT nx-1,ny-1; PAPER 6; OVER 1;" "
210 RETURN
220 DATA 128,z,z,z,z,z,z,255,128,190,160,190,130,190,128,255,z,193,247,z,z,z,255,z
Just like the previous version, it will first generate a random map like this:
Except this time it will ask for multiple source and target positions. Notice the number of sources and targets doesn't make any difference in the map processing time.
After the entire map is processed, the program will show, for each source position, a path towards its closest target:
You can download a TZX file with both versions here.
I'm now considering to implement a Z80 assembly routine for practical use in games, before moving to the next algorithm. Is there any interest on this?
2 ways:
count the length of the path, this can't be longer than all fields.
Mark all fields, when no move possible to unmarked field, no way possible.
I used the first method in my version of MUSHROOMMAN to test if all transporters were linked in a circular way. The max number of transporters is 10 so when more moves were done, the alligning was circular and therefore an illegal move.
These algorithms will always find the (best) solution if it exists. If it cannot find a solution, it means there's a problem in your map...
First of all, it's easy to notice when it happens. In algorithm #49, if there's no solution it will explicitly show the message "NO SOLUTION!". In algorithm #51, if one of the source positions don't have any valid path to any of the existing targets, it simply won't draw any path for this source. Or alternatively, in both cases you can just check if d(row,col) is zero.
So how can you avoid maps that don't have a solution? It depends:
If it's an automatically generated map, you better use a "perfect maze generator" (that produces map that always have a solution) like this. Even if you prefer more "open" maps with several paths, you can still use this algorithm, then randomly destroy a few more walls afterwards.
If you are designing maps "manually", make sure all areas are accessible. Otherwise, if you prefer to leave a few inaccessible areas intentionally, then mark them somehow (perhaps using a different INK or PAPER?) such that, during the game, you can easily avoid placing source or target positions there.
If you prefer to ignore these suggestions, there's even another possibility: after you generate your map, randomly choose a target position, then run algorithm #51 once. After this, d(row,col) will contain distance from target (if accessible) or zero (if not accessible). Now you can randomly choose sources and other targets among positions where d(row,col) is not zero, so you can be sure all these positions will be accessible from each other. However this alternative doesn't work so well because, without a good "maze generator", your map may contain too many inaccessible areas...
Comments
This is the reason A* is almost always the best choice for modern games.
However the situation is different for Spectrum games. They are limited to such a small playing area that, in this case, quadratic behavior is not a problem.
Good point. The level must have enough obstacles to require taking small detours (if it's too empty then there's no need for pathfinding), but it still has to be fairly open with many possible routes otherwise the "intelligent choices" in A* won't help.
It would be interesting to look at a practical example. I thought the most obvious example would be Pac-man, but when I simulated A* using this, it seems A* needed to process about half the map in many situations. I'm guessing a map size close to 24x32 is not big enough for A* to provide a significant difference. Here's an example:
In this case, even if my algorithm always processes all positions, each iteration only has to be 2 times faster than A* in order to achieve better results in worst cases. And I'm sure it would be a lot faster than this.
PS: I forgot to mention that simply processing all positions will work even better for this kind of game, because a single execution of my algorithm will be enough to find the shortest route for all 4 ghosts towards the player position!
Can you suggest other examples? It would be interesting to simulate them.
The pseudo-code change is trivial:
pathfind2(position SOURCE, position DESTINATION) { create empty [strike]QUEUE[/strike] [B]WHATEVER[/B] clear array DISTANCE[] mark DISTANCE[DESTINATION] = 0 add DESTINATION to [strike]end of QUEUE[/strike] [B]WHATEVER[/B] while [strike]queue[/strike] [B]WHATEVER[/B] is not empty remove POSX from [strike]start of queue[/strike] [B]WHATEVER such that it's the position with minimum (distance from DESTINATION + estimated distance from SOURCE)[/B] [B]if POSX is same as SOURCE then return "PATH FOUND"[/B] for each [strike]unmarked[/strike] [B]unblocked[/B] position POSY, that is neighbor of POSX [strike]if POSY is same as SOURCE then return "PATH FOUND"[/strike] [strike]DISTANCE[POSY] = DISTANCE[POSX] + 1[/strike] [B]distY = DISTANCE[POSX] + 1[/B] [B]if POXY is unmarked or DISTANCE[POSY] > distY[/B] [B]DISTANCE[POSY] = distY[/B] [B]calculate estimated distance from SOURCE[/B] [B]if POSY is already inside WHATEVER move POSY inside WHATEVER else[/B] add POSY to [strike]end of QUEUE[/strike] [B]WHATEVER[/B] return "THERE'S NO PATH" }The problem is, the extra Z80 assembly code required to manage whatever data structure you choose (that supports repeatedly inserting elements and extracting current minimum element according to calculated heuristics) will make the implementation above several times slower than the original pseudo-code.
OK, I agree this "bucket sort" data structure is a very good choice for A*. Even so, I still believe it's not worth it.
The problem is, you are applying asymptotic analysis to a limited size problem (i.e levels limited to size 24x32). Therefore the value of these constants make all the difference.
For comparison, my algorithm only requires a single circular buffer. The best implementation would use a 256-aligned area of 256 bytes, with register HL pointing to first element and DE to next available position.
Here's the entire code to add an element to end of queue:
The entire code to remove an element from start of queue:
The entire code to calculate queue size (or check if it's empty):
And the entire code to create queue and already add the first DESTINATION element:
Even if the actual algorithm implementation requires using IX/IY instead of HL/DE, or storing 2 bytes instead of 1, it won't be much different than this. In a Spectrum game, this should be fast enough to always process all level positions in a single frame.
I'm sure that implementing the data structure you proposed would be several times slower than this, Therefore, whenever A* requires processing a significant percentage of the map (such as the example in my previous post), it could take a very long time to finish.
:)
You are welcome! :)
Not at all. The size of the level plays no role in the analysis. Perhaps you should re-read that...
Do you suggest that your implementation can't deal with paths longer than 255 bytes? Or how exactly do you encode one of the 768 nodes into 8 bits?
Edit: Ah, I noticed you mentioning the two bytes. Makes me wonder why claim it can be implemented like this when it can't...
Anyway, I am getting kind of tired of this debate. I just wanted to provide hints about A* to anyone interested, not to argue about your preferred algorithm...
Patrik
Well, 24*24 vs 3*12 still looks like big difference to me, even for the trivial example I gave...
Nice visualiser, BTW. The reason why A* shows little advantage is because the area is a maze like, so each algorithm works basically the same as I mentioned before. The only difference you can get are the additional optimizations like jumping to corners along direct lines etc. to limit the amount of nodes inserted, not the search as such.
Try to apply it to something like this or this or any other CCS war game and you will see how much does BFS/Dijkstra suck...
That's just an unprooven claim. Might be true, might be not. I am not going to waste my life trying, though. Perhaps Bob Smith might tell us how fast he was able to implement it...
Patrik
You misunderstood me.
Of course asymptotic analysis doesn't depend on level size, and that's the most important characteristic of any algorithm to solve problems with arbitrary size. However Spectrum maps don't have arbitrary size. They are limited to a maximum size of 24x32.
For instance, if we have an algorithm that solves a certain problem in time N*N, and another that solves it in time 10*N*log2(N), according to asymptotic analysis the second option is obviously much better as a general solution. However, if you are going to implement it in a machine where always N<=32, then the first option becomes a better choice in this case.
This is the reason I said that maximum Spectrum level sizes are so small that the constants make all the difference.
No. I just suggested that it's never necessary to store more than a hundred "pending neighbors" in the queue at the same time, thus a circular buffer of 256 bytes will be large enough.
In my Pac-man example, notice there's no need to consider every single character as a valid position. It would be enough to only take into account positions at the relevant rows/columns, as follows:
This way, the algorithm can process it like a 10x12 map. This way, a single byte would be enough to store each coordinate, and processing will be a lot faster. The result won't be exact since a few passages are slightly longer than others, but I doubt the player would notice the difference.
However, in games where this kind of simplification doesn't apply, I agree it's necessary to store 2 bytes instead of 1 for each queue position. That's something I mentioned in my previous post.
I though this was an interesting technical discussion. I agree it doesn't make sense to turn this into an argument!
Yes it's a big difference. Even so, if each iteration of A* is 16 times slower than each iteration of my algorithm, then it's still not worth it.
I suspected A* didn't have enough advantage because the map wasn't large enough, despite providing multiple paths. But I really don't know. Can you suggest a 24x32 map that would be a better example?
If we consider any individual screen from these games, A* doesn't seem favorable either.
But do you mean finding a path across the entire game (i.e. for enemies moving through several screens)? If so, A* would be clearly the best choice. All my previous comments only apply to maps up to 24x32. However, are you sure any of these games really have multi-screen pathfinding? It's really surprising that any Spectrum game can afford to dedicate enough memory and processing time to do that.
It would be very interesting to have an optimized A* library for the Spectrum. Too bad this won't happen! :(
Really? I don't get how you can come to such conclusion. The latter ones are typical examples of a grid with variable terrain costs, with few impassable areas (depending on the unit type). A* should ace Dijkstra in such environment with ease...
Why don't you take on the challenge yourself, then? :)
Patrik
BTW, this wouldn't work unless you would change how you choose the next node to process and include reevaluating of node's cost when processing neighbors. Otherwise your algorithm might fail to find the shortest path...
Patrik
You may not need A* if your map is static and number of goals are small. Look up the "smelly algorithm" (IIRC) that can let you store best direction for each position in the map. The idea is simple: the goal position emits a stink of strength zero that grows by 1 for each step taken from the goal. You can traverse the map from the goal and store the stink at each map position before the gameplay begins so that the map stores best direction to the goal (decrease stink by 1) for every map position.
Sorry if this has been mentioned before, I don't have much time for Sinclair stuff these days,.
Write games in C using Z88DK and SP1
Different terrain types (i.e. pathfinding with "weighted" positions) is a different matter... see below.
Because I don't even think A* for the Spectrum would be worthwhile (although interesting) as you may have guessed from my previous posts :)
No, there's no need to reevaluate costs. In this case, the idea remains exactly the same as I wrote in #21: first process all positions that are 1 step away from the goal, then all positions 2 steps away from the goal, then 3, etc.
In the example above, if you are processing all positions 3 steps away from the goal, and you find a mountain neighbor, then it should be marked as "6" instead of "4". Afterwards, the mountain neighbor will have to wait longer than other neighbors, until it's turn "6". And that's perfectly fine!
I previously provided in #27 a detailed explanation for the most efficient implementation for regular maps. Now I will provide a similar explanation for maps with irregular terrain. But first, let me explain the data structure we will need.
Let's consider we have 3 types of terrain, as I mentioned above: "path" that takes 1 step to move, "forest" that takes 2 steps, and "mountain" that takes 3 steps. In this case, instead of 1 queue, this implementation will require 4 stacks. Notice that stacks are more efficient than queues, since they can be located anywhere (there's no need for boundary alignment or anything), and we only need a register per stack storing the address of its first element (we can simply put $ff at the bottom to mark the end of each stack, so it's easy to check if it's empty without using another register or even remembering its initial address).
These 4 stacks will be called STACK[0], STACK[1], STACK[2] and STACK[3]. They will initially store positions that are 0, 1, 2, or 3 steps away. In practice, it means STACK[0] will contain the positions that we are currently processing, we will put their "path" neighbors in STACK[1], their "forest" neighbors in STACK[2], and their "mountain" neighbors in STACK[3].
After we finish processing all positions from STACK[0], then all stacks addresses are "rotated", such that STACK[1] becomes STACK[0], STACK[2] becomes STACK[1], STACK[3] becomes STACK[2], and finally STACK[0] (now empty) becomes STACK[3]. Then we repeat the process. This way, we will be now processing all positions 1 step further away from the goal, without the need to recalculate anything.
Here's the pseudo-code for this implementation:
pathfind(position SOURCE, position DESTINATION) { create empty stacks clear array DISTANCE[] mark DISTANCE[DESTINATION] = 0 add DESTINATION to top of STACK[0] repeat while STACK[0] is not empty remove POSX from top of STACK[0] for each unmarked position POSY, that is neighbor of POSX if POSY is same as DESTINATION then return "PATH FOUND" n = TERRAIN[POSY] DISTANCE[POSY] = DISTANCE[POSX] + n add POSY to top of STACK[n] rotate stack addresses until all stacks are empty return "THERE'S NO PATH" }Of course this implementation will be somewhat slower than #27 since it requires a few extra operations, but probably not much. And each iteration of this algorithm should be still much faster than each iteration of A*.
Which solution works better? It depends on how many positions A* will need to process. If A* processes only a few positions, then A* will certainly finish faster. However if A* needs to process a significant percentage of the map, then the faster iterations in my algorithm above should help it finish faster, even if it has to process all map positions (assuming a Spectrum level size limited to 24x32 as usual).
The problem with A* is, I suspect the analyzed area in A* will be even larger in an irregular terrain. Whenever A* finds a forest area or a small mountain, the analyzed path will naturally start expanding sideways, so A* will try multiple routes crossing the mountain and also attempting to walk around it. If it was a very large map, then it would not matter that A* was processing a long path that is a few positions wide, because this path would still represent a very small percentage of the total area. However, if the map is only 24x32, then a path a few positions wide would cover most of the map! Anyway too bad I could not find an online simulator for this situation, it would be fun to watch this working.
Finally there's another advantage for using my algorithm instead of A* in this situation: irregular terrains are typical of strategy war games. These games always have multiple troops at different locations. Since my algorithm can mark distance from goal for every map position, a single execution will be enough to find the shortest path for each enemy soldier towards a player position. Even better: if the player also has multiple soldiers at different positions, my algorithm can be executed for multiple destinations. You would just need to initialize STACK[0] with all these destinations. This way, a single execution would be enough to determine, for each enemy position, the shortest path to its closest player soldier! This would not work in A*.
Sure, it's certainly doable. The question is, would it be really worth it? For typically small 24x32 Spectrum maps, probably not.
For further details you would have to read the entire thread...
OK, that's pretty much how the algorithm I described works. :)
The implementation details (intended for Z80 assembly) were presented in #21, #27 and #34 if you are interested.
It's good to have you back anyway!
I see - so you consider it 6 steps away, even if it is 4 steps away.
In that case what you are describing is no different than the A* I have described above - your 4 stacks is the sliding window of the bucket sort like array I mentioned. Ergo the implementation can be entirely the same, except that you don't add the heuristics which guides you towards the goal into the mix, and thus have to needlessly process much more nodes. Seems like pretty obvious loss to me.
Two points:
- why should all units in a strategy game head toward single point?
- you can use A* to find multiple paths at the same time as well. Just swap start and destination and use multiple starting points.
Patrik
Welcome back Alcoholic Anonymous! Please tell me what should I do with the Abbaye project.
As you know I've finished all the background stuff for the rooms. At the moment another coder is working on a new code for the game, but from scratch. If you tell me how, I can continue with your code, putting the enemies/ collisions/events.
If not, I hope that the coder will finish the project.
Is everything ok?
Write back soon,
D.H.
Exactly!
Not really. There's a lot more work involved in A*. Here's a list:
Now here's the animation for A*:
Notice that the first search advances in all directions. This would be really bad if you imagine this scene as just a very tiny "zoomed in" part from a giant map. In comparison, A* is considerably smarter and moves towards the goal, which would work much better as part of a giant map... However, now imagine both scenes are already showing the entire map. In this case, the first search visited about 95% of the entire map, and A* visited "only" about 65%. Considering that each iteration of A* is slower and it uses a lot more memory, if it has to visit most positions anyway it means A* is not worth it in small maps!
In a Dune-based RTS, you could activate a thumper device to temporarily attract all sandworms towards this single location, ignoring all human troops for some time...
But I agree with you here. Strategy games typically require multiple sources and targets. This is another advantage of algorithm #44 since processing time is essentially the same regardless of how many sources and targets, unlike A*.
Not really.
If you start search from multiple locations towards a single goal, each one of them will usually start with different costs, thus using 5 stacks won't be enough. Therefore you will need much more than 9K as temporary memory, or use a slower, more complex data structure.
The alternative (search from a single location towards multiple goals) [strike]won't work because this won't give a consistent heuristic[/strike]. EDIT: Ops! I just realized I was wrong about this. The same heuristics should be valid. The problems in this alternative are different. If you use A* to search towards multiple locations, it will only find the route to the closest one, instead of providing solutions for all of them in a single execution. It will also require even more processing, since every iteration will need to calculate estimated distance to all goals to compare them. Another problem is that multiple goals should drive A* search towards multiple directions, thus ruining the main advantage of A* (i.e. directing the search only towards the goal instead of moving towards all directions).
However strategy games typically require multiple sources and multiple targets. The computer troops usually choose a few important targets, then move each attack unit towards its closest target. I can't see an efficient way to implement multiple sources and multiple targets in a Spectrum game using A*...
Therefore I have implemented the "simplified Dijkstra" algorithm from post #27:
This is just a simple implementation in BASIC, therefore too slow for practical use. I will rewrite it in assembly later... Even so, this BASIC version is quite useful as a demo, so people can see how it works in practice, and it should be easier to understand the source code.
When you run this program, it will generate a random map like this:
At this point, if you are not happy with the generated map, you can simply export the screen from the emulator, edit it in ZX-Paintbrush, and import again. You don't even need to use the same colors: every char position with a dark PAPER (colors 0,1,2,3 without BRIGHT) are interpreted as obstacles, everything else as paths.
Afterwards you must choose a single source and target, then you will see the pathfinder in action. During execution, neighbor positions stored in the queue are marked in yellow, and already processed positions are marked in cyan. If the map has a valid solution, the program execution will finish like this:
You can download the TZX version of this program here.
Even so, I made a small change to previous implementation so it now supports multiple sources and multiple targets. In practice, it only means that this variant will calculate paths for the entire map, without bothering to check the source positions at every step:
Just like the previous version, it will first generate a random map like this:
Except this time it will ask for multiple source and target positions. Notice the number of sources and targets doesn't make any difference in the map processing time.
After the entire map is processed, the program will show, for each source position, a path towards its closest target:
You can download a TZX file with both versions here.
I'm now considering to implement a Z80 assembly routine for practical use in games, before moving to the next algorithm. Is there any interest on this?
Quite easy.
2 ways:
count the length of the path, this can't be longer than all fields.
Mark all fields, when no move possible to unmarked field, no way possible.
I used the first method in my version of MUSHROOMMAN to test if all transporters were linked in a circular way. The max number of transporters is 10 so when more moves were done, the alligning was circular and therefore an illegal move.
These algorithms will always find the (best) solution if it exists. If it cannot find a solution, it means there's a problem in your map...
First of all, it's easy to notice when it happens. In algorithm #49, if there's no solution it will explicitly show the message "NO SOLUTION!". In algorithm #51, if one of the source positions don't have any valid path to any of the existing targets, it simply won't draw any path for this source. Or alternatively, in both cases you can just check if d(row,col) is zero.
So how can you avoid maps that don't have a solution? It depends:
- If it's an automatically generated map, you better use a "perfect maze generator" (that produces map that always have a solution) like this. Even if you prefer more "open" maps with several paths, you can still use this algorithm, then randomly destroy a few more walls afterwards.
- If you are designing maps "manually", make sure all areas are accessible. Otherwise, if you prefer to leave a few inaccessible areas intentionally, then mark them somehow (perhaps using a different INK or PAPER?) such that, during the game, you can easily avoid placing source or target positions there.
If you prefer to ignore these suggestions, there's even another possibility: after you generate your map, randomly choose a target position, then run algorithm #51 once. After this, d(row,col) will contain distance from target (if accessible) or zero (if not accessible). Now you can randomly choose sources and other targets among positions where d(row,col) is not zero, so you can be sure all these positions will be accessible from each other. However this alternative doesn't work so well because, without a good "maze generator", your map may contain too many inaccessible areas...Agreed.
All algorithms discussed in this thread are already using this second option.
Done. You can read about it here.
Write games in C using Z88DK and SP1
I hope you like it :)