Algorithm for staying "alive" forever

| | August 4, 2015

I am implementing a game where the player is playing(sliding) the little red rectangle and the purpose is to not hit the black rectangles and to not move out of the inner blue rectangle. The black rectangles are moving in trajectories from left to right(right to left) and from top to bottom(bottom to top). The speed they are moving with is constant e.g. 5 pixels. You can get a better idea in this video.

One of the game modes is the following – 2 paths will be proposed by the game displayed as arrows and one of them may lead to “death”, while the other will always be the right one and the user will have to choose one of them until he makes the wrong choice. The movement directions can only be top,bottom,left or right and not diagonal and the speed of the red rectangle is constant e.g. 6 pixels and the black rectangles speed is 5 pixels.
I am struggling with the algorithm for the “successful” direction for more than a week and what I have done so far is the following :

  • Generate a random float number between 1.0 and 2.0 seconds and then divide the generated number by 0.030 for example to get the number of moves that will be made by the black rectangles and red rectangles.
  • Calculate the black rectangles and red rectangle move points that will be made for the following time session by multiplying the number of moves by the speed which is 5px for the black rectangles and 6px for the red rectangle.
  • After I know the speed of the black rectangles and the number of moves I can tell their position in any time of the current time session.
  • Move the red rectangle to the left until it is being hit and remember that result e.g. 15 moves until hit. Do the same thing for right,up,down direction.
  • Sort the direction by the moves that can be made before hit in ascending order.
  • Move the red rectangle in the direction in which the most number of moves can be made.
  • Do the same thing until the time session ends i.e. the random float number generated in the first step.

    This solution works most of the time, but some times it leads to a position where an escape is not possible. The problem is not in the code, but in the algorithm logic.
    For example look at the following image : Stuck situation


As you can see the red rectangle will go to a position where it will be stuck by two of the black rectangles. The best possible solution in this situation would be to move to top 1 time and then to left and after that to top, because the black rectangle in the top left corner is going to top, but I really have no idea how to solve this task. What would be the optimal way to accomplish this task.

Thank you in advance!

One Response to “Algorithm for staying "alive" forever”

  1. I would try using a heuristic. From what I can tell there are at most 5 areas to move around in and 4 passages between them. As the bars move around, the 5 areas, we will call them, top, left, center, right, and bottom, are either expanding or contracting. Your heuristic could be based on whether an area is expanding or contracting. Obviously, it would be preferable to move into an area that is currently expanding. Actually, the most optimal area would be behind one that is expanding while the area clockwise to it is contracting. In other words, you will have the most time to maneuver in to and out of an area that is behind a bar that just left the edge and is moving towards the center, while the bar clockwise to it is moving from the center to the edge.

    Examining your picture, the optimal place to move to would be behind the left bar. As you move up one, and then to the left, a space will open up behind it. At this time the top bar is moving up and out of the way. This gives you plenty of time to move around.

    So your heuristic could work like this: 1)an area is most desirable when the bar for that area is at the edge of the screen. As the bar moves towards the center and back towards the edge, that area becomes less desirable. 2) A passageway is most desirable right after the bar that blocks it starts moving from the center to the edge. It decreases in desirability as it moves to the edge and back towards the center.

    You can then move the red block towards the most favorable passage to the most favorable area.
    The value of your heuristic can be arbitrary. What is important is that it makes sense. You can have it to be a value of 100 when the bar is at the edge. By the time it reaches the center it the value could be 50. And as the bar heads back out to the edge it could drop down to 0. Or perhaps when the bar reaches the center the heuristic is 75, and when the bar get halfway back to the edge it is 50. Then as it gets closer to the edge it starts increasing. This might give you a chance to start moving in the right direction ahead of time.

    Just to be clear, what I am calling a passage would be the region just above the left bar, the region to the right of the top bar, the region below the right bar, and the region to the left of the bottom bar.

Leave a Reply