Thread: concurency

Concurrency Project

A simple computer game allows game characters to move around a 2D space discretized into a grid, with each character or obstacle fully occupying a grid cell, and each character moving atomically to adjacent cells. Given a destination, characters search for the shortest path to their destination and attempt to follow that plan. Once they get to their destination, or if they cannot reach their destination at some point, (perhaps because another character has moved into the way) they pause a turn, and then choose a new destination and calculate a new movement plan.

Model each character as a thread, initially distributed around the perimeter of an m×m grid, and given random destinations. Each character moves discretely, at 20ms intervals, although movement rates otherwise just depend on thread scheduling. Obstacle cells are never chosen for destinations, and paths are calculated with Dijkstra’s or any other convenient shortest-path algorithm, ignoring the current position of other characters.

Provide an obstacle map for your simulation. The map should have a random r cells set to obstacles such as in the Figure shown below. Note that obstacles are never within two squares of the perimeter.


Figure 1 - Red dots show perimeter-distributed characters whilst the black squares show the obstacles

Your application should take n and m as parameters, in that order and construct a simulation of n characters on an m×m grid. A visual depiction is not required, although you may find it helpful for debugging. It should always be possible for characters at least 2 squares away from each other to move concurrently, and movement must be atomic. Explain why your simulation does not deadlock.

Try your simulation for m= 20 and m= 100, and values of n and r that produce sparsely populated and densely populated situations. Let each simulation run for 2 minutes. Once the simulation has ended report the total number of moves made by each character