Created during a computer OOP course during the second year at Ariel University in the Department of Computer Science, 2018
Project site: https://zvimints.github.io/OOP_3/.
Made by: Zvi Mints and Or Abuhazira
 |
 |
Problem: Given a .csv file with pecans and fruits find a minimal optimal greedy path by the time such that the Pacmans will pass through all the fruits in the map This project represents a greedy solution to the problem.
So let's start!
MyFrame package is divided into 2 classes
the first "Menu" class is the Menu class that represents the GUI of the side Menu in the right side, the second "DotsandLines" class is the Game Panel that represents the Game in the left side.
This Class is responsible for actions between Objects of the kind Point3D. The Class is used to Provide a solution for elementary actions between vectors and points in R^3 Vector space.
File_format This package is divided into 2 classes.
- CSVToMatrix: This class is responsible to make Dynamic matrix[][].
- Game2KML: This Class Game Object into KML file.
Fruit This Class represent Fruit that implements GIS_Fruit. Every Fruit has FruitData which include relevant information about the Fruit such that ID, Also Geom Element which represent the location of the Fruit in [Lat, Lon, Alt] coords. Each Fruit was created through Runtime of Game Class.
Pacman This Class represent Pacman that implements GIS_Pacman. Every Pacman has PacmanData which include relevant information about the Pacman such that ID, Speed, Radius, Color and Time.
- Note: Time used to represent The total time of the Pacman's walk in the chosen route by the Algorithm.
Also, Geom Element which represents the location of the Fruit in [Lat, Lon, Alt] coords. Each Pacman was created through Runtime of Game Class.
- Each Pacman have Pacman thread the represent the movement of the Pacman by real time in the Game Panel, each thread is responsible to transfer himself to the destination point by the vector that in the current Path
- we can change the "real-time" running algorithm by the time that each thread will sleep
This class can convert Pixel point to Geo Point and back.
Each map containst Map Map (Image) that represent the background of the Game.
Each path has relevant information about a path between 2 Points in R^3.
Each path has the coordinates of source port and destination port.
In addition, the path contains the vector and the time that the path is taking to a Pacman, we can know which Pacman take which path by the ID that the path is saving, each path have a color that set up by Pacman color.
- Game: This class represent Game which include Fruits List and Pacmans List, this class can init Pacmans and Fruits from Matrix.
- GameToCSV: This Class Converting Game into CSV file.
- Game2KML: This Class Converting Game into KML file.
This package is responsible to convert from a game that has been runned by the algorithm and make a valid. KML file that shows the path's of each Pacman
Example:
 |
 |
The algorithm of the project a greedy algorithm:
Problem: for input number of pacmans and the input number of fruits we want to find the minimum route time such that all fruit will be eaten by the pacmans.
Solution: (Pseudo code)
GreedyAlgorithm(Game game)
1. Init all pacmans time to 0
2. While fruit list is not empty
3. for each Pacman find the closest fruit to him by time, enter the value to the array
4. find the minimum time in the array as a function of (current pacman time + time to next fruit)
5. move Pacman to (Fruit - Pacman radius) point, update all the fields and add path to the solutions
6. remove Fruit from the fruit list
Complexity: O(|F| * |P| * |F| )
- GameTest: Testing the Game Package.
- Map Test: Testing the Map Package.
- MyCoords Test: Testing the Coords package.