User253751's answer is good for the example you've given but in a more advanced map it'll break easily. The problem with that idea is that if you have 2 paths joining together doesn't matter where, The enemy will have to choose either one or the other, and it'll have to know which direction is the end. Now this sounds easy and all "just have it go the direction the end is in" but its not that simple. There could be situations in which the paths wont be in the direction making that map broken. As a programmer you have to make sure that no matter what, your program wont break.
Totally the easiest way would be to revamp the way you enter your map into the program. have a csv type data structure with numbers telling you the next directions
0 for wall
1 for up
then you just put those numbers in. if not wall then tile. numbers correspond to next tiles. easy directions without any algorithm business. File to read would look something like this for your example:
Really easy to implement and read. You read every digit for every tile. if has 5 then tile is start. if has 6 then is end. the rest are direction digits for the nexts vector. This way you can also easily implement splits by just putting more than one direction digit next to each other. each number is each tile here: 52 is start tile direction right. The nexts vector is a vector in each tile that acts a bit like your linked list showing you the next tiles from that tile you're on in a way of showing the direction to go to from there. Enemies can pick randomly from any of the tiles in that next tile to go to.
OR if you want to do something harder:
I suggest a little different approach:
- have a 2 dimensional array (a matrix) which will store each tile
- have the tiles have an array of 'nexts'
- the nexts will only store next path tiles
- the vector of nexts will be the direction in which to move
- you load in the walls and tiles into the vector normally via if # emplace back tile with value or desc "wall" if not #, then path etc etc
- now you need to know the direction in which to go. Let each tile have variable 'visited' which will be bool value.
- in loop go from start to finish adding next tile to vector of nexts of previous tile. Set current tiles' visited to true.
- for split path add both next tiles to that tile and for every of those nexts recursively continue same program.
- when 2 paths join happens program will think its a split. let it continue,
- when the above join as 'split' happens, it continues UNTIL it goes back to the actual split before. if the actual split before's next is the tile you're on A.K.A. if you're going in the opposite direction than the split says, recursively back track your steps to the joing that was understood as a split and end that loop. ending that loop and returning those visited bool values back to zero will enable the previous split to continue to the join. I'll try to explain with pictures:
On the picture above, On each tile it checks the tiles next to it. If its tile AND its not visited, next for current tile is that next tile. Repeat.
No problems here. Will always work
For each split, it recursively does the same thing as for single...
split 1 path 1 split 2 path 1:
split 1 path 1 split 2 path 2
split 1 path 2 split 2 path 1
split 1 path 2 split 2 path 2
So above i showed you every possible turn it could do. By themselves they dont do much but if you stack them, they give you the paths.
so first the first image is done, Its fine cool and all. Then the second is done on top of the first. But the first split has nexts vector as up AND down. Since we are going up and the first split is visited and has opposite direction, WE CANCEL and revert back to second split from which we came from and we stop that iteration of recursion.
We're left with image 1 again. Then since we exhausted every recursive next in the second split, the recursion rolls back to previous split to complete it's next's. Image 3 is tried. image 3 fails because that tile above the second split has already been visited and has opposing direction already too. if it was already visited, we stop that iteration of recursion. Image 4 is tried. Same idea as image 3. we get to split that has been already visited so we break and stop there. No more recursions left so we finish the recursive loop completely. We're left with the path for any amount of splits and joins.
This might not be the best option and with bigger and really complex maps it might not fully 100% work but with some tweaks on that level of difficulty i think it will be fine.