DSA2020-Zombie-Simulator

发表于 | 分类于
完成数据结构需求，包括Zombie Simulator, Skip List Set, Deque以及Redix Sort, 量比较大。

Using the UML below, create a class called Human which represents a human being whom can walk around a simulated world.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Human
# x,y : double
# dx,dy : double
# size : double
# isAlive : boolean
+ world_width, world_height : int
---------------------------------
# max_speed : double
# sightDistance : int
# generator : Random
# others : List<Human>
---------------------------------
+ Human(others:List<Human>, x:double, y:double)
+ run(): void
+ getX(): double
+ getY(): double
+ getSize() : double
+ kill() : void
+ draw(g : Graphics) : void

Each Human can run as a separate thread and maintains an x,y position with periodic movements using dx, dy which change slightly after a number of iterations. A Human can be instantiated using an initial position and a list of all other humans in the world. A Human can be drawn using the draw method and passing a Graphics object around its x,y position and size. There are also a static public fields which can be set to determine the size of the world in which humans roam.

Create a Zombie class which extends a Human. Try to work out what Human fields/methods should be overridden. A Zombie has a sight distance of the entire panel and will actively seek and search out the nearest human, it will then alter its dx,dy movements towards the closest human for a fixed period of time before checking if there is any other targets it could possibly chase. A Zombie can only move half of the max speed as a human. If a Zombie manages to catch a human it will bite and kill the human.

Modify the human class so that it tries to move away from the closest zombie within its sight distance by modifying its dx,dy speed. A Human sight distance is only of the world size.

Create a GUI called ZombieSimulator with two buttons, starting either a zombie or a human as a thread. The GUI should periodically redraw all Human and Zombie objects moving within the world. It should maintain a single thread safe data structure for all Zombie and Human objects. It should also periodically check if a human has been killed by a zombie, in which case it re-instantiates the object as a new Zombie thread. See below for an example screenshot, where zombies are red squares and humans’ blue circles.

Feel free to add any private/protected helper methods across any of the classes which you feel would improve the design of your program and play with any of the formula constants (eg sight distance, max speed, sleep time) to improve the feel of the simulator.

A skip list data structure is a modification of a singly linked list so that the add, contains, and remove methods are O(log2 n). Essentially it consists of a series of singly-linked lists L0, L1, …, Lk, usually visualized one on top of another with L0 at the bottom. The list L0 holds all the (nonnull) elements of the collection in order with null at the start and end of the list. Each list Li+1 holds a subset of the previous list Li and has links from each element down to the same element in the previous list. These links enable elements in the collection to be found more efficiently than by just traversing the list L0. The illustrated skip list holds three elements e0, e1, e2 in comparable order:

When an element is added to the skip list it is first randomly decided in how many of the lists it will appear (it is always placed in the list L0, and if in a list Li it has a 50-50 chance of also being in Li+1 and so on). Then the correct insertion place is found in the topmost list to which it will be added (which might result in a new top list being created), and then working downward it is added to each of the lists below. An element is found by starting at the top list (referenced by firstNode), following the next links until either the element is found, the end of the list would be reached, or else the element would be passed. If not yet found, a down link is followed to continue the process with the list below. To remove an element the element should be removed from each list in which it appears (starting with the topmost list).

Using the UML below as a guide, prepare a class called SkipListSet that extends AbstractSet (and so implements the Set interface) using a skip list data structure and the following UML diagram as a guide. Include a suitable main method which effectively tests your skip list implementation.

A screenshot of an example test is shown below, note that for convenience and debugging purposes the skip list toString prints all node elements on each level.

A deque (pronounced deck) or double-ended queue, is a linear collection that allows insertion and removal at both ends. The interface above called DequeADT, available from Blackboard, is an abstract data type which can hold any generic element E, it also describes operations for a deque.

Create two data structure implementations of the Deque, one which uses an underlying array called ArrayDeque and one which uses an underlying dynamic doubly-linked structure called DoublyLinkedDeque. Implement the deque data structures yourself, do not use extra Java Collection classes!

For efficiency first, last, enqueueRear, enqueueFront, dequeueRear, dequeueFront, clear, size, and isEmpty should all be O(1) operations. Feel free to add any necessary private helper methods and a suitable toString which returns a string representation for your deque implementation.

Further enhance your classes to make sure all methods are safe from unexpected events using appropriate exception handling (example, if user code tries to remove something from the deque when empty, it should throw an appropriate exception). Create a test class with a suitable main method which effectively tests all operations on one or both deque implementations.

See the screenshot below for an example of testing one of the deque implementations.

Radix sort is a sorting algorithm that focuses on sorting parts that comprise the number rather than the whole number directly. Usually it can only be used on fixed digit or character inputs such as post codes or county codes. Radix sort focusses on each digit/char at a time and placing it in a desired queue shared with other parts of the same value. After all elements are queued, it polls all elements back into an original list. It repeats this process k times where k is the amount of digits/chars that comprise the element. However, if we had to sort a single digit element across a larger range of possibilities (eg Ascii or Unicode values) then a different strategy for radix sort can be utilised at a bit level, instead focussing on the bits which make up the data type.

Create a simple static method called bitwiseRadixSort which takes a char[] of Unicode values and sorts them looking at the individual bits which form each char data type. Include a main method to test using randomly generated char values as demonstrated with the screenshot below. Note it may be beneficial to print out the Unicode number as well as the printed char so that you know your sort is working.