\section{Pathfinding}
When moving units in the world of JWars a navigational problem arises when finding the shortest paths between to points. There exists a range of solutions when finding the shortest path between to points. These solutions however have different requirements for the map in which to navigate and some might be inconsistent in speed.
Most of todays RTS games solve this problem by using a tilesystem for the map and designating tiles with either 'used' or 'free' as markers when scanning through the map with an algoritm. This approach has several advantages, like high and consistent speed, while it requires a predefined map-structure to search in. A good example is the A* algorithm which is a shortest path graph algorithm. For finding a shortesth path using graphs for data representation will be the best way. When finding a path on a map you will need fixed points (reference points) designating where to turn and to make heuristic evaluations during the search. A graph is normally represented like this:

\[G = ( V , E ).\]

// indsæt illustrationer

$V$ is a list or other representation of all the \emph{vertices} in the graph
$E$ is a representation of the \emph{edges} in the graph. An edge is best seen as a link between two vertices - meaning that you can go from vertex $v1$ to vertex $v2$ using the edge $e(v1,v2)$. The weight of an edge, corresponding to the amount of time it takes to traverse it, is given by a weight function $w: E \mapsto [0, infinity]$ since a distance already travelled can not be negative.

Given a graph with a chosen data structure there are multiple ways to solve the single-source shortest path problem from vertex $A$ to $B$. Most of these algorithms are based on selective expansion of the search area since this type has the best running times with the fewest vertices visited.

The pathfinding in our instance has some requirements to the algorithm which we must take into account before implementing a final algorithm.
The most pressing issue is to convert the dynamic and rather limitless implementation of units and other objects in the world of JWars. We have chosen to a very open approach in the area of unit location and building placement. Any building or unit is placeable anywhere on the map and will not fill out a certain amount of tiles. The option of letting objects take space in the map can not be done in JWars, since the data structures allows object of \emph{any} size in JWars. With the no limitations in size of objects, or the speed the can have, tiles can be partially covered and still count as 'filled' in a  pathfinder. This system is however implemented in some games and works well - these games however the above mentioned limitations in object sizes and placements of static objects.

A tile system is incapable of handling the pathfinding in JWars - the aspect of pathfinding on graphs is still viable and the most efficient method. The implementation we have chosen for the pathfinding is to transform the dynamic/open implementation of the JWars-world to a graph-system on which we can perform a search algorithm. For accomplishing this we have implemented a dynamic graph system explained in the next chapter.

For every path needing to be found we start with the given graph for the current map $G = ( V, E )$.
V consist of all corners on static objects convex hulls on the map. This data is stored in the collion map.
$E$ starts of as an empty list. 
\footnote{If it were to be a pre-defined list it should consist of all possible routes between any vertices on the map. This amount of data would be hard to handle and if the amount of static objects were large enough it would require alot of memory space.}

The start and goal location are added to the program as Sloc and Gloc - these are considered vertices which is set for each running of the algoritm. In general pathfinding A* is considered the most effective search algorithm on the single source shortest path problem. In effect this means that the algorithm will terminate as soon as the shortest path has been found to the given goal vertice. There exist a number of algorithms to solve the problem but the A* algorithm has the shortest running time and fits or problem profile well in the almost greedy expansion of the search tree. 

In theory all edges can be represented in $E$ - but not active until discovered by the algorithm. Using this approach we expand the graph according to A* and evaluate it as such. The operation that makes this algorithm stand out is the shoot-to function which activates vertices/edges while searching for the path.

Here is pseudocode for the importent functions in the pathfinder.

\begin{verbatim}
boolean Shoot-to(Sloc, Gloc)
	// When shooting from a vertice to another we will at some point either 
	// collide with the goal or another object on the map
	If(collider = goal)
		backtrack
	else FindVertices(collider, angle(Sloc, Gloc))

FindVertices(vertice, angle)
	// max/min are the points in the collider with the most extreme angle 
	// values from the original angle
	Shoot-to

\end{verbatim}

When solving this problem the algorithm only takes into account static objects which are registrered in the as static list in the collision tiles. Unfortunately moving objects has the possibility of making