Defining our key modules

So I think there are couple of key components that is involved in my project. I imagine there are 3 modules that each has a specific task. The key components are the following :

1. API
2. FE
3. Simulator
4. DB

So we have seen earlier the API and FE. lets talk about simulator, it will be the bread and butter of the project. It'll control the creation of journeys, it will control and move cars etc...

---

Simulator

So let's create a simulator module to our traffic simulation repo and let's talk about some of the main functionalities.

Controlling the data on a map

So in order to control and be able to display it on a map, we use openstreetmap that gives us access to download a geojson data file for a slice on a map. I have chose a slice of downtown kyiv. Of course this dataset needs to be filtered to remove anything that we are not interested in. The main thing we need is roads so we write a script and get a processed new geojson file. Now that we have this file with only the data we need, we have to translate it to some sort data-structure that we enables us to

• Validate if selected random points is valid ( A valid journey is where we can reach B from A)
• Find fastest path based on some weight
• Make movement 1 step at a time from point A to B
• Be fast and efficient

So after some research the best DS I found is a Graph. Because we can directly access a specific starting point via a key (like a hashmap) and also move to all adjacent points. In other words if we have point A on a road like this --------A---------- we can quickly access point A and know adjacent points which helps us move one step forward or backward.

Creation of Journeys

So the creation of journeys meaning a ride from Point A to B, it consists of multi step process to finally have a ride created.

First we have to pick up two random points, we do this via PostGIS more on that later but let's assume our simulator receives two random points. Its not guaranteed that we will be able to reach our destination as we are only within a slice. So we have to validate, and we use simple BFS algorithm to check whether a destination is reachable

func PathExists(start, end dto.PointNode) bool {
	fmt.Printf("Validating our point before persisting : %f %v\n", start, end)
	visited := map[dto.PointNode]bool{}
	queue := []dto.PointNode{start}

	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]

		if node == end {
			return true
		}

		for _, neighbor := range datastructures.RoadMapGraph[node] {
			if !visited[neighbor] {
				visited[neighbor] = true
				queue = append(queue, neighbor)
			}
		}
	}

	return false
}

If the func above returns true we persist in our DB where it gets polled later.

Polling

We keep polling from our DB any newly created journeys so we pull them and start to process them this is does through multiple process via API as only the API module interacts with the DB.

Find best route

Now that we have a valid journeys, we will have to build the best path that start from point A and reaches point B.

There are two options here, Dijkstra or A*. Lets define and discuss what they are and the key difference :

Dijkstra's Algorithm:

Dijkstra's Algorithm is a pathfinding algorithm used for finding the shortest path between nodes in a graph, which may represent, for example, road networks. It works by visiting the nearest unvisited node, examining its neighbors, and updating their distances from the starting point. The algorithm continues until all nodes have been visited.

A Star Algorithm:

A* (A-Star) Algorithm is also a pathfinding algorithm, but it introduces a heuristic into the mix. It calculates both the cost from the start node and an estimated cost to the goal, allowing it to prioritize paths that seem closer to the goal.

Differences:

Heuristic Function: The key difference is A*'s use of a heuristic to estimate the distance to the goal, making it generally more efficient for pathfinding in spaces where the goal is known.

Efficiency: A* can be more efficient than Dijkstra’s in many cases, as it often explores fewer nodes.

Use Case: Dijkstra’s is used when you need the shortest path to all nodes, while A* is preferred when you have a single destination.

Now I must admit understanding A star was not the easiest thing so for anyone trying to grasp it I recommended this explanation https://www.happycoders.eu/algorithms/a-star-algorithm-java/

Now in terms of performance A star shines when there are a lot of nodes, while mine is just under 14,000 which did not have any significant performance gains.