Weighter Graph (Node) + A*

[SosoLaMojo]

Introduction

Our task is to implement the A* algorithm on a weighter graph for the 5204 module.

---

Weighter Graph

class Node

• float gCost
• float hCost
• float fCost
• array neighbors
• NodeType type

Methode NodeGeneration

Creation of dead or alive nodes at different positions (Vector2f).

Methode SetNeigtbors

Give its neighbors to each node (scenario: 4 neighbors per node)

Methode SpawnEntities

Set a point of start(A) and end(B) (Vector2f)

---

A*

Methode FindPath

Calculate and store the nodes of the path found by A*.

• Methode Distance
• Methode ManhattanDistance

Questions

• What is the best way to store neighbors? Pointer or Array?

  • What is the best way to store the path? Pointer or Vector Array?

[EliasFarhan]

Thanks for the enhaucement proposal.

Some remarks:

• Please use the correct name, it is a Weighted Graph.
• I don't understand the point of the gCost, hCost and fCost? I have some sort of an idea why you use them, but they don't need to be stored with the node as they are only useful when doing A, so they should be stored temporarily when calling the function. Please don't mix the data that you need to define a graph and the temporary data of the A algorithm.
• Does the Node have a position?
• How will you store the Nodes? If you say std::vector inside the WeightedGraph, please be sure not to reference neighbors with raw pointer but with indexes to avoid invalidation on vector resize.
• To answer your neighbors question, you will probably have to store the neighbors in an std::vector to avoid setting limits (std::array does require compile-time length)
• What is the NodeType? If I am remembering A* right, there is no such a thing as NodeType...

Please do response with a more complete proposal such that I can continue to help you be sure how you implement your proposal.

Useful reference:

• http://theory.stanford.edu/~amitp/GameProgramming/

[SosoLaMojo]

Introduction

Our task is to implement the A* algorithm on a weighter graph for the 5204 module.

---

class Node

• std::vector neighbors
• Vector2f position

class Map

• std::vector graph

Methode AddNode

Add nodes to map

Methode FindPath

Calculate and return the nodes of the path found by A*.

[EliasFarhan]

Thanks for the update.

Be sure to implement at least Dijkstra algorithm (A but without arrival heuristics) by Thursday (A would be great, but I want first to be sure you set up your data structures correctly).