Algorithms in Save My Cheese

In this post, I will go into the algorithmic details of Save My Cheese. The game consists of several sub-problems:

1. Drag and snap shapes.
2. Calculate path from where the mouse is to cheese location. Pathfinding has to take obstacles (unpassable cells) on map into account.
3. Update map when user places a piece in its place, i.e. make that portion of map unpassable so that a new path to cheese might be needed.

Drag and snap shapes: This can be further divided as follows:

1. Create puzzle pieces (polygons) and their respective snap locations.
2. On mouse click: Check if there is a polygon at mouse click location by using Polygon.contains() method.
3.  On mouse drag: Move the selected polygon by translating it by currentMousePos-prevMousePos
4. If selected polygon center to snap polygon center is less than prespecified distance, make the center location of polygon equal to snap polygon.

I wrote a small demo that you can download here.

Calculate path: I used the A* algorithm, you can read more about it here. I also wrote a small demo program that animates A* pathfinding, you can download it here.

Update map and paths when a piece is placed: When the user snaps a puzzle piece into place, that portion of the map becomes unpassable and some or all of the mice might need to update their paths to the cheese. The problem is to detect which map cells lie under that piece and change their type to unpassable, a.k.a wall. I wrote a demo that handles that, you can download it here.

p.s. Initially I used separate threads for each mouse as an exercise in multi-threading. Later, I used a simple game loop. You can download the multi-threaded version here.