Algorithm for "Frogger" game [closed]

Question

This is an interview question. Design an algorithm to play "Frogger". That is, you direct a frog, which has to cross a busy road. The frog can move forward/backward and left/right, the cars move only left, and both frog and cars move one position at a time.

I wonder how I can reduce it to some basic well-known algorithm. If there were no "time" in the game, I would build a graph of safe positions and find a path to the frog destination. However, I cannot use this approach.

How to reduce "Frogger" to a well-known problem?

Answer 1

Assuming that the cars and the frog move discreetly, one 'square' at a time, let's denote the number of times the frog has moved vertically (across the road) by V and the number of times the frog has moved horizontally (along a lane) by H. If you have say, 5 lanes, 1-5, the frog can be on lane X at time instants of the form T=X + 2*V + H. So far, so good.

Since the state of the cars on each lane at a time instant T is deterministic, we can generate the state of the entire road for a reasonable amount of time in the future: L(1,T)L(2,T)...L(5,T). I would suggest that you generate fictive road states of the form L(1,1 + 2*V + H)L(2,2 + 2*V + H)...L(5,5 + 2*V + H) and look for a state in which you have an open straight line to the other side, therefore eliminating the time component.

In effect, you are brute-forcing it, but there is no reason why you shouldn't, assuming a reasonable number of lanes and permitted moves.

Answer 2

I would guess something like this would work in a simple form. (Assuming this is an for how to run the game, as opposed to how to solve it)

1) build array to store all tiles on map (each segment of road / water / log)
2) build list to store car / log locations
3) Set up a timer
4) on timer tick, update array of locations with full/empty tiles for each car / log in list (2)
5) check whether the current locaiton of the frog is in the same location as a log / car
6) repeat 4/5 while frog can move

something like that?