Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
Do you want to program something like a "for of war" and randomize what's behind it when revealing it? –  Markus von Broady Oct 19 '12 at 19:46
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. –  Byte56 Oct 19 '12 at 19:50
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. –  Gustavo Maciel Oct 19 '12 at 20:09
@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. –  Byte56 Oct 19 '12 at 20:21
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 –  joxnas Oct 19 '12 at 20:45
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
Has that already been proved? Oh wow i should find the paper and read it through. Thank you –  y26jin Oct 19 '12 at 19:34
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.