So suppose we stand on a position(x0, y0) of a map. We can only move on the horizontal plane(no jump and stuff) but we can move forward, left, or right (in a discrete math way, i.e. integer movement).

As soon as we move to the next position(x1, y1), everything around us is generated randomly by a program. We could be surrounded by one of mountain, lake, and road. We can only move on the road. The road is always 2D as the map itself.

My question is, are we able to play this game endlessly? "End" means that we come across a dead end and the only way out is to go backward.

  • \$\begingroup\$ Do you want to program something like a "for of war" and randomize what's behind it when revealing it? \$\endgroup\$ Oct 19, 2012 at 19:46
  • \$\begingroup\$ Your description is a little misleading. You say we can only move forward, left or right. Then say that the next position from (0,0) is (1,1). That indicates a diagonal move. \$\endgroup\$
    – House
    Oct 19, 2012 at 19:50
  • 3
    \$\begingroup\$ mvps.org/directx/articles/catmull here's one article that the guy explains how to use catmull rom splines, and for bonus, he gives a simulation where he generates an endless road with splines. don't know if this is exactly what you're looking for, but worth a look. \$\endgroup\$ Oct 19, 2012 at 20:09
  • \$\begingroup\$ @GustavoMaciel Good link. I should note that I removed some important information when I edited the title. This is a discrete math type question. Essentially, tile based movement, not free movement. So splines don't apply in this situation. My fault, not yours. \$\endgroup\$
    – House
    Oct 19, 2012 at 20:21
  • \$\begingroup\$ So we are in a tile and we see the 8 tiles around us which can be walkable or non walkable. When we go to one of the walkable ones, are the 8 around it regenerated randomly (Meaning the tile we were previously can change) ? Or are the tiles we never saw the only ones that are generated? Cause if it is the first option the question doesn't make much sense.. You need to explain yourself better \$\endgroup\$
    – jmacedo
    Oct 19, 2012 at 20:45

1 Answer 1


Perhaps I'm not understanding your question, but this is really not a math question at all.

The answer is yes, we could go on "forever" if the algorithm for generating the road allows it. It depends entirely on the how the random generation occurs. The algorithm for randomly generating the road and landscape can easily be tailored to never end.

If the selection of mountain, lake and road was truly random each time. There is a high likelihood that you would eventually turn back on your path. So it would depend on how you define handling that situation. If you're allowed to overwrite the previous tiles then you wouldn't have a problem. However, if you're not allowed to overwrite tiles then eventually the path would end. It would loop back on itself and you would be forced to stop.

  • \$\begingroup\$ Has that already been proved? Oh wow i should find the paper and read it through. Thank you \$\endgroup\$
    – y26jin
    Oct 19, 2012 at 19:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .