There are two possible ways to run the program:
swipl -s game.pl -g methodname_entry_point -t halt
, where instead ofmethodname
should be substituted eitherrandom
,backtrack
orbfs
. In this case input will be imported frominput.pl
file.- Comment
:-[input].
in the very beginning of the file and runswipl -f path_to_input -s game.pl -g methodname_entry_point -t halt
where instead ofpath_to_input
path to the input file (or it's name if it is in the same directory as game.pl) should be specified.
- Field is always 20x20. However, it can become smaller size using orcs as margins.
- Player cannot pass directly to the touchdown, only to another human
- All search algorithms are uninformed. They try to go/throw on each direction
- Random search make 100 tries, each take at most 100 turns. By turn we mean throw, going to adjacent cell, but not rotation and not passing by ball. If it didn't succeed after 100 tries, it terminates.
- Backtracking return the best possible path, not the first found. Thus, it runs until all possible paths observed.
- As third search algorithm I use bfs, which is basically A*, but with zero heuristic. Heuristic cannot be determined for uninformed search, and that is why this algorithm is applied.
- There can be several touchdowns, but not zero
I've implemented three search algorithms: Random Search, Backtracking and Breadth-first search. Before going through algorithms, I'd like to mention some functions that are reused in all algorithms:
This function is used to append to existing path new turn. It just prints to Output
existing path + new turn :
add_turn_to_string(Throw, X, Y, Path, Output) :-
swritef(Output, '%w\n%w%w %w', [Path, Throw, X, Y]).
The following function performs logic of throw: it recursively checks all coordinates in given direction and if there is a human in this direction, terminates with true and assigns to passed value new coordinates:
throw(X, Y, Xnew, Ynew, DirX, DirY) :-
Xn is X+DirX, %find new coordinates
Yn is Y+DirY,
not(orc(Xn, Yn)),(
( human(Xn, Yn) % if it is human, return values
-> Xnew is Xn,
Ynew is Yn
; ( Xn>=0, %if no, check validity of coordinates and recursively perform check again
Yn>=0,
Xn=<19,
Yn=<19
),
throw(Xn, Yn, Xnew, Ynew, DirX, DirY))
).
This Algorithm is very easy. It doesn't make any assumptions, just pick random turn out of all possible (for example, we exclude going downwards if y=0). All rules are preserved: if we come to the cell with human, we do not count next turn, on orc we lose, on touchdown win. Ball can be randomly thrown out in the direction where there is no human, this counts as lost try. This leads to not really high performance on big maps, where touchdown is many turns away from (0, 0). Also, as throws have probability of 1/3 to be performed on the first turn, if there is a human nearby to the touchdown that is one throw away from (0, 0), there is very big chance to succeed in 100 tries. Runtime is almost constant ~0,035 sec. For example, consider the following map input1.pl
:
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
T | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | T | . | . | . | . | . | . | . |
H | . | . | . | . | . | . | . | . | . | H | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | H | . | . | T | . | . | . | . | . | . |
Here, with best-possible score 4, we get such statistics:
95% of got scores are between 6 and 9.
Obviously, if length of optimal path is longer, for example this map
input2.pl
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
T | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | T | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | T | . | O | . | . | . | . | . | . | . | . | . |
Then only in ~1/3 runs some path, not always optimal, is found.
But adding some humans to the same map we can increase this chance to ~50%:
input3.pl
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | H | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
T | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | H | H | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | H | . | . | . | . | H | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | H | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | H | . | H | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | H | O | . | . | . | . | . | . | . | . | . |
. | H | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | H | . | . | . | . | . | . | T | . | O | . | . | . | . | . | . | . | . | . |
And if we make our map even more complicated, let's say only one touchdown far away from start, the chance of getting a solution is neglectable. Needs to say, that other methods as well do not lead us to solution, as they take to This is example:
input4.pl
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | T | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | H | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | H | . | . | . | . | . | . | . | . | . | . |
. | H | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | H | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
Only 2 runs out of 200 was successful. |
More maps with statistics of each method on every map will be in appendix, here are just some basics.
This method has really good performance for small maps. For example, on 10x10 map it usually takes no more than 3 seconds to run. However, for input1.pl
it takes 33 seconds to finish, as map is quite big. Of course, by our assumption all maps are 20x20, but still we can place orcs as a borderline. Some comparison of performance:
input5.pl
takes 13-15 ms to traverse all paths.
. | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
. | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O |
H | . | T | O | H | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
H | . | . | . | O | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | H | . | H | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | O | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
for input6.pl
it takes 30-40 ms
. | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
. | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . |
O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O |
. | . | . | O | H | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | H | . | . | T | . | O | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | O | . | O | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | H | O | . | . | . | . | . | . | . | . | . | . | . | . |
H | . | . | . | H | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . |
Observe input7.pl
. There are quite a lot of paths, but as there is a path of length one, which can be easilly found, when our backtracking finds this path it throws away all paths that are longer, so the runtime is just 10 ms
. | . | O | O | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
O | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . |
. | O | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | O |
. | . | O | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | O | . | O | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | O | . | . | . | O | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | O | . | . | O | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | O | . | . | O | . | . | . | . | . | . | . |
T | . | . | . | . | . | O | . | O | O | . | . | . | . | . | . | . | . | . | O |
. | . | . | . | . | . | . | . | . | O | . | . | . | . | . | O | . | . | . | . |
O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O |
. | . | . | O | . | . | T | . | . | O | . | . | . | . | T | . | . | . | . | O |
. | . | . | . | . | . | . | . | . | T | . | . | . | . | . | . | . | . | . | . |
. | T | . | . | . | . | . | . | . | O | . | . | . | . | T | . | . | . | . | . |
. | . | . | . | . | O | . | . | O | O | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | T | . | . | . | O | . | . | . | . | . | . | . | . | . | . |
. | O | . | . | . | . | H | . | . | O | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | O | T | . | T | . | T | . | . | . | . | . |
. | . | . | . | . | O | . | H | T | O | . | . | . | O | . | . | . | . | T | . |
. | T | . | . | . | . | H | . | . | O | . | . | . | H | . | . | . | . | . | . |
However, if we remove this touchdown, runtime will be greater:
input8.pl
takes about 40 ms
. | O | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
O | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . |
. | O | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | O |
. | . | O | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | O | . | O | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | O | . | . | . | O | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | O | . | . | O | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | O | . | . | O | . | . | . | . | . | . | . |
T | . | . | . | . | . | O | . | O | O | . | . | . | . | . | . | . | . | . | O |
. | . | . | . | . | . | . | . | . | O | . | . | . | . | . | O | . | . | . | . |
O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O |
. | . | . | O | . | . | . | . | . | O | . | . | . | . | T | . | . | . | . | O |
. | . | . | . | . | . | . | . | . | T | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | O | . | . | . | . | T | . | . | . | . | . |
. | . | . | . | . | O | . | . | O | O | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . |
. | O | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | T | . | . | O | T | . | T | . | T | . | . | . | . | . |
. | . | . | . | . | O | . | . | . | O | . | . | . | O | . | . | . | . | T | . |
. | . | . | . | . | . | . | . | . | O | . | . | . | H | . | . | . | . | . | . |
input9.pl
, which is 12x12, takes 1.5s to run
. | . | . | . | . | . | . | . | . | . | . | . | O | . | . | . | . | O | T | . |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
. | . | . | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . |
. | . | . | . | O | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . |
T | . | . | . | . | . | . | H | . | . | . | . | O | . | . | . | . | . | . | . |
. | . | H | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | . | O | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | O | . | . | . | O | . | . | . |
O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O |
. | . | . | . | . | . | . | . | . | . | . | . | O | . | O | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | T | . |
. | . | . | . | O | H | O | . | O | . | . | . | O | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | O | . | . | . | O | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | O | . | . | . | . | T | . | . |
. | . | O | . | . | T | . | . | . | . | . | . | O | . | . | . | . | . | . | . |
. | . | . | . | O | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | O | . | . | . | O | T | . | O | . | . | . | O |
. | . | . | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | O | . | . | O | . | . | . | . |
input10.pl , which is 16x16, takes about to 15s |
. | . | . | O | . | O | . | . | . | . | . | . | . | . | . | . | O | . | . | . |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
. | . | . | . | . | . | . | . | . | . | . | . | . | O | . | . | O | . | . | . |
. | . | . | . | . | . | . | . | . | . | O | T | . | H | . | . | O | . | . | . |
O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O | O |
. | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | O | . | . | . |
. | . | . | . | . | . | O | . | . | . | . | O | . | . | . | . | O | . | . | . |
. | . | O | . | . | . | H | . | . | . | . | . | . | . | . | . | O | . | . | . |
. | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | O | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | O | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | O | . | . | . | O | . | . | O |
. | . | . | . | . | . | . | O | H | . | . | . | O | . | . | . | O | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | T | . | . | . | . | O | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | O | . | . | O |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | O | . | . | . |
. | . | . | H | . | . | . | . | . | . | . | . | . | . | . | . | O | . | . | . |
. | . | . | . | O | T | . | O | O | T | . | . | . | H | . | . | O | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | O | . | . | . |
. | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | O | . | . | . |
. | . | H | . | . | O | . | . | . | . | . | . | . | . | . | . | O | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | H | . | . | O | . | . | . |
just a random 20x20 map input11.pl
even more, 4m 30s
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | H |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
. | . | . | T | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | H |
. | . | . | . | . | T | . | . | . | O | . | . | H | . | . | . | . | . | O | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . |
. | . | . | O | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . |
O | T | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | O | . | . | . | . |
. | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . | O | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | O | . | . | . | T | O | . | . | . | H | H | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | H | . | . | O | O | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | O | . | . | . |
. | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | O | . | . | . |
. | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | T | . | . |
Maps like input4.pl
are too hard to solve, after 40 min I've dropped test as it is unreasonable long to count as solution.
This algorithm in prolog requires a lot of unnicessary in other languages calculations, it's quite imperative, but still works. For input1.pl
runtime is also about to 30ms, but in input2.pl
it takes more than 1 minute. Again, all important statistics will be in appendix, but it is important to say that bfs has quite similar to random search requirements, but it does not fail on hard maps, just take too long to run.
In my implementation there is no vision, we just observe all accessible cells and test them. For sure, if implementation taked into account environment around cell, for some maps that take too long to complete there can be improvements (not for random, it is still random). But on average it gives only constant time improvement, while complexity depends on size of map exponentially, so this couple of maps that will run faster are neglectable. Example of such map is input4.pl
, where backtracking can see touchdown from edge and quite rapidly find the shortest path (but only if we throw away paths longer than current, full backtracking takes ages almost on every big map). For algorithms I have there is no map that become unsolvable because if the solution exist both backtracking and bfs will find it, even though it may take ages.
As I said in part 1, there is no completely unsolvable maps (except maps like input12.pl
and input13.pl
, where there is no way to reach touchdown), but there are some maps that will take quite a long to process.
input12.pl
:
. | H | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
. | . | . | . | O | . | . | . | . | . | . | . | H | . | . | H | O | . | . | . |
O | . | . | . | O | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . |
. | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | O | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . |
. | . | . | . | O | H | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | O | . | . | . | . | H | . | . | . | . | H | . | . | O | . | . |
. | . | . | . | O | . | . | . | . | . | . | . | . | . | T | . | . | O | . | . |
. | . | . | . | O | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
O | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | O | . | . |
. | . | . | O | O | . | . | . | . | . | . | . | . | . | . | . | . | . | T | . |
. | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | O | . |
. | . | . | . | O | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . |
O | O | O | O | O | T | O | O | O | O | O | O | O | O | O | O | O | O | O | O |
. | . | . | O | O | . | . | . | . | . | . | . | . | . | . | . | . | . | H | . |
. | . | . | . | O | . | . | O | . | . | H | . | . | . | . | . | . | . | . | . |
. | . | . | O | O | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | O | . | . | H | . | . | . | . | O | . | . | H | . | . | . | . |
input13.pl : |
|||||||||||||||||||
. | . | O | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . |
- | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | H | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | H | . | . | . | . |
. | . | . | . | . | . | . | . | . | H | . | . | H | . | . | . | . | . | . | . |
O | . | . | . | . | . | . | . | . | . | . | . | . | . | . | H | . | . | . | . |
O | . | . | H | . | . | . | . | . | . | . | . | O | . | . | . | . | . | O | . |
. | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | O | . | O |
. | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | O | . | O | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | O |
. | . | . | . | . | . | . | . | . | . | O | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
O | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | H | . | . | . | . |
Hard to solve maps are big, sparse (not a lot of humans and orcs), has no short solution, so that backtracking cannot process it in a minute, must take more than 8 turns for optimal solution, so that random search will rarely find such a solution and bfs will take to long to process. The easiest example is just one touchdown somwhere close to the center.
file | random search | backtracking | bfs | comment |
---|---|---|---|---|
input1.pl |
almost 100% success;0.02s runtime | 33s runtime | 0.029s runtime | map is big, but pash is short, so random ans bfs perform better than dfs |
input2.pl |
0.022s runtime, but only 30%success | 0.022s runtime | 1 min20s runtime | map is bounded, so backtrack is very fast |
input3.pl |
same runtime, 40% success | 2.8s runtime | >10min | more humans - better for random search, but a bit harder for others because of a lot of successful throws. Especially for bfs |
input4.pl |
same runtime, less than 1% success | ~ | ~ | very hard map for dfs, bfs |
input5.pl |
about to 50% success | 0.013ms | 0,009ms | very easy map for all |
input6.pl |
13% success | 0,032ms | 2.8s | again, bounded map with reasonably long path is ok for all except of random, for which path of length 6 is rather complicated |
input7.pl |
100% success | 0.008ms | 0.009s | nothing to say, next |
input8.pl |
5-7% | 0.04s | 6min50s | optimal path of length 8, hard for bfs and random |
input9.pl |
2-3% | 1.8s | ~ | path of 9 - too hard for bfs and random |
input10.pl |
10% | 15s | 22s | path of length 6 |
input11.pl |
couple of percent | 4min30s | ~ | 20x20 map |
input12.pl |
~ | ~ | ~ | impossible |
input13.pl |
~ | ~ | ~ | impossible |
input14.pl |
9% | ~ | 6.77s | randomly generated 20x20map, ok for bfs, but too hard for backtrack |
input15.pl |
100% | 0.018s | 0.010s | path of length 2, easy for all |
input16.pl |
almost always optimal solution | 0.008s | 0.015s | lentgh 4, again nothing interesting |
input17.pl |
almost 100% to find solution, but very often it is twice longer than optimal | 0.06s | 0.94s | length 5, but a lot of humans and touchdowns randomly spreaded, so random shows different result each time |
input18.pl |
see input17 | 0.05s | 0.94s | see input17.pl |