One of the most common problems in video games is determining the fastest route

Question

One of the most common problems in video games is determining the fastest route from 2 positions. In

this assignment, you will look at how to determine that route efficiently using a simple graph that describes the connections between the nodes.

The data file for this assignment will be formatted as follows:

Line 1: The number of nodes in the map (we will call this N).

Line 2 to N+1: The weights for the connections for each node in the graph. The value of -1 indicates there

is no direct path between the current node (the row being read) and the target node (the column being

read). Note that the value of 0 is possible, and the weight to go from any node to itself will always be 0.

Lines N+2 and following: Each line represents a pair of nodes. The first is the target position and the

second is the current position.

For each (current, target)

pair, you must find the fastest route in the graph.

REQUIREMENTS

1.Complete the Game::FindFastest function in the game.cpp file to find the shortest path betweenpositions.

2.The algorithm should be as close to linear time as possible!

//Game.h

#pragma once
#ifndef __GAME_H__
#define __GAME_H__

#include <iostream>
#include <queue>
#include <vector>

class Progress
{
public:
   int Position;
   int Weight;

   Progress() : Position(0), Weight(0) {}
   Progress(int pos, int weight) : Position(pos), Weight(weight) {}

   bool operator> (const Progress& right) const
   {
       return Weight > right.Weight;
   }
};

typedef std::priority_queue<Progress, std::vector<Progress>, std::greater<Progress> > PriorityQueue;

class Game
{
private:
   std::vector<std::vector<int> > m_Map;
public:
   void LoadMap(std::istream& is)
   {
       int numRows = 0;
       is >> numRows;
       m_Map.resize(numRows);
       for (int i = 0; i < numRows; ++i)
       {
           m_Map[i].resize(numRows);
       }

       for (int i = 0; i < numRows; ++i)
       {
           for (int j = 0; j < numRows; ++j)
           {
               is >> m_Map[i][j];
           }
       }
   }

   int FindFastest(int currentPos, int targetPos);
};

//Game.cpp

#include <climits>
#include "game.h"

int Game::FindFastest(int currentPos, int targetPos)
{
   int numRows = m_Map.size();
   std::vector<int> bestSoFar(numRows, INT_MAX);
   PriorityQueue toBeProcessed;
   toBeProcessed.push(Progress(currentPos, 0));
  
   while (!toBeProcessed.empty() && bestSoFar[targetPos] == INT_MAX)
   {
       // fill in algorithm to find lowest weight to target position from current position
   }
   int weight = bestSoFar[targetPos];
   return (weight < INT_MAX) ? weight : -1;
}

Explanation / Answer

#include <climits>
#include "game.h"

int Game::FindFastest(int currentPos, int targetPos)
{
int numRows = m_Map.size();
std::vector<int> bestSoFar(numRows, INT_MAX);
PriorityQueue toBeProcessed;
toBeProcessed.push(Progress(currentPos, 0));
bestSoFar[currentPos] = 0;
  
while (!toBeProcessed.empty() && bestSoFar[targetPos] == INT_MAX)
{
// fill in algorithm to find lowest weight to target position from current position
int u = toBeProcessed.top().position;
toBeProcessed.pop();

for(int v = 0; v < numRows; v++){
int w = m_Map[u][v];
if( (w > 0) && (bestSoFar[v] > bestSoFar[u] + w)){
bestSoFar[v] = bestSoFar[u] + w;
toBeProcessed.push(Progress(v, bestSoFar[v]));
}
}

}
int weight = bestSoFar[targetPos];
return (weight < INT_MAX) ? weight : -1;
}

// for any doubt please comment

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.