3.Classes - Orcohen33/Pokemon_Game GitHub Wiki
Click to expand!
- This class is a simple class that represent location.
| Methods | Details |
|---|---|
| x(),y(),z() | return double variable |
| distance() | calculate distance from me to other point3D |
-
This class is a simple class that represent a vertex on a directed weighted graph and implement a Set of simple operations.
-
Each node contains few fields:
- Location: An object that represent the location of the node by (x,y,z).
- Weight: A variable that is help implement other methods for calculations.
- Info : A variable that used to implement other methods.
- Tag : A variable that used to implement other methods.
- Key : A unique key that is used as each node's ID.
| Methods | Details |
|---|---|
| getKey() \ setKey(int key) | Get or set key of the Node |
| getLocation() \ setLocation(GeoLocation p) | Get or set location of Node |
| getWeight() \ setWeight(double w) | Get or set weight of Node |
| getTag() \ setTag(int tag) | Get or set tag of Node |
| getInfo() \ setInfo(String s) | Get or set info of Node |
Click to expand!
-
This class implement a set of operations applicable on a directional edge(src --> dest) in a (directional) weighted graph.
-
Each edge contains few fields:
- src: A variable that represent the id of the source node of this edge.
- dest: A variable that represent the id of the destination node of this edge.
- w: A variable represent this edge weight (positive value).
- info: A variable represent this edge remark (meta data).
- tag: A variable represent temporal data.
| Methods | Details |
|---|---|
| getSrc() | Get the id of the source node of this edge |
| getDest() | Get the id of the destination node of this edge |
| getWeight() | Get the weight of this edge (positive value) |
| getTag() \ setTag(int tag) | This method allows setting the "tag" value for temporal marking an edge - common practice for marking by algorithms |
| getInfo() \ setInfo(String s) | Get or set info of Node |
Click to expand!
-
This class implement an directional weighted graph (Support a large number of nodes).
-
This implementation based on HashMap data structure.
-
Each DirectWeightGraph contains few fields:
- nodes: HashMap data structure that represent the groupd of nodes by their ID's
- edges: HashMap of Hashmaps data structure that represent each node group of directed outgoing edges in this graph.
- ingoing: HashMap data structure that represent each node group of directed ingoing edges in this graph.
- node_size: A variable that stored the amount of nodes in this graph.
- edge_size: A variable that stored the amount of edges in this graph.
- MC: Mode count a variable that stored the amount of changes that happend on graph (e.g remove node,add node ,remove edge .. )
| Methods | Details | Time Complexity |
|---|---|---|
| getNode(int node_id | Returns the node_data by the node_id | O(1) |
| getEdge(int src,int dest) | Returns the data of the edge (src,dest), null if none | O(1) |
| addNode(NodeData n) | Adds a new node to the graph with the given node_data | O(1) |
| connect(int src,int dest,double w) | Connects an edge with weight w between node src to node dest | O(1) |
| nodeIter() | This method returns an Iterator for the collection representing all the nodes in the graph | O(V) , |
| edgeIter() | This method returns an Iterator for all the edges in this graph | O(E) , |
| edgeIter(int node_id)This method returns an Iterator for edges getting out of the given node (all the edges starting (source) at the given node) | O(k) , k = size of outgoing edges of given node | |
| removeNode(int key) | Deletes the node (with the given ID) from the graph and removes all edges which starts or ends at this node. | O(k) , V.degree = k |
| removeEdge(int src,int dest) | Deletes the edge from the graph | O(1) |
| nodeSize() | Returns the number of vertices (nodes) in the graph | O(1) |
| edgeSize() | Returns the number of edges (assume directional graph) | O(1) |
| getMC() | Returns the Mode Count - for testing changes in the graph | O(1) |
| Methods | Details | Time Complexity |
|---|---|---|
| nodeOutEdges(int key) | Return true if this node have outgoing edges | O(1) |
| nodeInEdges(int key | Return true if this node have ingoing edges | O(1) |
Click to expand!
-
This class represents a directed (positive) weighted Graph and implement Theory Algorithms including: init,copy, isConnected, shortedPath , center , tsp and save&load with JSON file.
-
This implementation based on HashMap data structure.
-
Each DirectWeightGraph contains few fields:
- dwg : DirectedWeightedGraph that represent a graph.
- parents: HashMap data structure that represent each node and his parent
| Methods | Details | Time Complexity |
|---|---|---|
| init(DirectedWeightedGraph g) | Inits the graph on which this set of algorithms operates on | O(1) |
| getGraph() | Returns the underlying graph of which this class works | O(1) |
| copy() | Computes a deep copy of this weighted graph | O(V+E) V - Size of vertices , E - Size of edges |
| isConnected() | Returns true if and only if (iff) there is a valid path from each node to each | O(V+E) V - Size of vertices , E - Size of edges |
| shortestPathDist(int src,int dest) | Computes the length of the shortest path between src to dest | O(V+E* Log(V)) V - Size of vertices , E - Size of edges |
| shortestPath(int src, int dest) | Computes the the shortest path between src to dest - as an ordered List of nodes | O(V+E* Log(V)) V - Size of vertices , E - Size of edges |
| center() | Finds the NodeData which minimizes the max distance to all the other nodes | O(V^3) V - Size of vertices |
| tsp(List cities) | Computes a list of consecutive nodes which go over all the nodes in cities | |
| save(String file) | Saves this weighted (directed) graph to the given file name - in JSON format | |
| load(String file) | This method loads a graph to this graph algorithm |
isConnected()
Explanation
Checks if there a path between every ∀u,v ∈V , This algorithm used Kosaraju.
Kosaraju algorithm based on DFS .
-
What is it actually does? -> it count the number of strongly connected components
- DFS
- Transpose the graph
- DFS on transpose graph
- return True if SCC.size==1 (SCC = A veriable to count the number of strongly connected components contain in graph)
Time complexity = O(|V|+|E|) -> |V| = size of vertexes , |E| = size of edges.
shortestPathDist(int src,int dest)
<details>
<summary>Explanation</summary>
Checks what is the shortest path distance between given src,dest∈V , This algorithm used Dijkstra.
Dijkstra check what is the lower weight path to get from u to v.
In this program i implemented dijkstra with priority queue , which decrease the time complexity.
-
What is it actually does?
-
Set the "source" node weight 0.
-
Start to explore his neighbors.
-
Therefore, we will see if the weight of the neighbor is greater than the weight of this vertex and the weight of the tip that connects them. If so we will change the weight of the neighbor at the vertex weight + the weight of the edge.
-
Once we come across a neighbour who is also our destination , we will update his weight if necessary and return the weight of the neighbor who is also the destination.
-
If the weight isnt -1 it means that there is a path between given source and destination.
Time complexity = O(|V|+|E|*Log|V|) -> |V| = size of vertexes , |E| = size of edges.
-
shortestPath(int src,int dest)
Explanation
This method returns the shorest path between src to dest - as an oredered List of nodes :src -> v1 -> v2 -> ... -> dest.
This method will return null if there is no such path.
I used the same algorithm as shorestPathDist but this method I reversed the list that Dijkstra created.
Time Complexity : O(|V|+|E|*Log|V|) ->|V| - Vertices , |E| - Edges
Explanation
This class repesent agent object from given string by client server I've done a few methods to make the object easier to make.Methods |
Explanation |
|---|---|
| update(String jsonFormat) | Parse the string to variables in the object |
| setNextNode(int dest) | Set next node to go to by dest of curr edge |
| getNextNode() | returns the destination of the edge this agent is currently on |
Explanation
This class repesent pokemon object from given string by client server I've done a few methods to make the object easier to make. it has no methods only parse the string to pokemon object.Explanation
The client class is responsible for the connection between the player and the server and give to the user all the information about the stage of the game (type of graph, the information about the agents and Pokémon's, the time of the stage etc..).
This class has provided to us by our professor.
Explanation
It's the class that represents all the information sent from the client and makes sure to convert all the information from string to lists of objects, Also contains the graph received from the game run step.
DirectedWeightedGraph graphList<Agent> agentsList<Pokemon> pokemonsList<String> info
-
List<Agent> parseAgents(String agentsJSON, DirectedWeightedGraph g)- Parse string to agents objects. -
ArrayList<Pokemon> parsePokemons(String pokemonsJSON)- Parse string to pokemon objects. -
updateEdge(Pokemon pokemon, DirectedWeightedGraph g)- updates the 'edge' field of a given pokemon to the actual edge said pokemon is on -
isOnEdge(GeoLocation pos, EdgeData edge, int type, DirectedWeightedGraph g)- Check if pokemon on any edge and update it.
Click to expand
This is the primary class that manages the information between the client and the server and the GUI interface.
- HashMap<Agent, List> pathMap
- Client client
- AgentsNPokemons arena
-
void initGame(Client game)-> init the game before we start it, means that all the string details parse to objects. -
void moveAgants(Client game, DirectedWeightedGraph g)-> this method is tell to agent to move to other node it uses dijkstra algorithm to find the shortest path for the next pokemon -
void initPathMap()-> init the pathmap for every agent. -
int nextNode(DirectedWeightedGraph graph, int curr, Agent agent)-> this method is a help method formoveAgentsto choose the next dest for every agent -
DirectedWeightedGraph buildGraph(String graph)-> build graph from given string -
void updateScore()-> update the score that show up on gui.