Take the 2-minute tour ×

I have a little problem with theory so I hope that you guys will help me.

Imagine 2D game...You are some square and you have to go from start to finish. Between start and finish are some moving objects. They are moving vertically and horizontally with different speed from player and from each other. So, I need some algorithm for testing is there a chance for player to finish level, or is there some fault in level design. If you have more details please google "The Worlds Hardest Game", try that game and you will see what I need.

I think that I could use A* algorithm for finding path and somehow customize it for working with static and moving boundaries, but I dont know how and is it even possible.

Cheers :)

share|improve this question

2 Answers 2

One approach to solve it as 'regular' Shortest Path problem is to increase the dimensionality of the problem.

Let's say you have a grid, so your graph is actually consisting of vertices:V={(x,y) | for each x,y on the grid} and edges E={(v1,v2) | can move from v1 to v2 in a single step }.
The above is for 'regular' static graphs.

In your problem, add another dimension - time. (so, instead of every vertex represent only 2 dimensions, it now represents 3!). You will get the graph G=(V,E) as follows:

  • V = {(x,y,t) | for each x,y and t}
  • E={ ((x1,y1,t),(x2,y2,t+1) | if you can move from (x1,y1) to (x2,y2) in time t}
  • Assuming the moving objects have some pattern, you will can modify it to E={ ((x1,y1,t),(x2,y2,t+1%m) | ... } (where m is the 'circular' repeat.

Now, you have yourself a classic shortest path problem in a graph. If your original source and target are (x_source,y_source) and (x_target,y_target), in the modified problem you need to go from (x_source,y_source,0) to (x_target,y_target,~) (where ~ is "don't care").

This problem is sovleable by A* like you said, with manhattan distances (on x,y only) as the admissible heuristic function.

share|improve this answer

I think it could be done with basic path finding algorithms - you just have to make sure to calculate obstacle positions correctly for each state.

share|improve this answer
This is not so trivial as you put it. path finding algorithms work on static graphs traditionally, where edges don't change.. –  amit Feb 12 at 23:53

Your Answer


