fork download
copy 
  1. #include <iostream>
  2. #define MAX_CELL 64
  3. #include <cmath>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8.  
  9. struct Cell {
  10.         int m_Row;
  11.         int m_Col;
  12.     };
  13.  
  14.  
  15. class CellTracker
  16. {
  17.  
  18.     //Establish String to hold all coords, separated by |~|
  19.     public: std::vector<Cell> seenCells;
  20.     public:
  21.     bool seenCell(Cell tCell, bool storeCell)
  22.     {
  23.         bool isFound = false;
  24.         //int length = 0;
  25.         for(unsigned int i = 0; i < seenCells.size();i++)
  26.         {
  27.             if ((seenCells[i].m_Row == tCell.m_Row)&&(seenCells[i].m_Col == tCell.m_Col))
  28.             {
  29.                 isFound = true;
  30.  
  31.             }
  32.         }
  33.         if (storeCell && !isFound)
  34.         {
  35.             seenCells.push_back(tCell);
  36.         //cout << "test" << endl;
  37.         }
  38.         return isFound;
  39.     }   
  40. };
  41.  
  42. class PathFindingForTest
  43. {
  44.     Cell finalCell;
  45.     int cMult;//this is an int that will containt either a +1 or -1, controlls movement on Column axis
  46.     int rMult;//this is an int that will containt either a +1 or -1, controlls movement on Row axis
  47.     float avgCost;//this is just for testing purposes, shows average cost of entire array
  48.     float CostSoFar = 0.0F;//stores the length/cost/weight accumulated so far
  49.     float cellCost[MAX_CELL][MAX_CELL];//stores original cellCost
  50.     CellTracker visited;//stores visited cells, TODO increase weight of visited
  51.     CellTracker badCells;//stores cells that I shouldn't visit again, TODO cut arrays once badCell is found
  52.     CellTracker final;//stores cells that declare final path
  53.  
  54.     bool moveVert(Cell currCell)//Tells direct path if it should move vertically
  55.     {
  56.         float cDiff = finalCell.m_Col-currCell.m_Col;//holds the column distance between current cell and end cell
  57.         float rDiff = finalCell.m_Row-currCell.m_Row;//holds the row distance between current cell and end cell
  58.         cMult = cDiff >= 0? 1:-1;//updates the column multiplier with a positive or negative 1, to tell the shortest path finder which way to go
  59.         rMult = rDiff >= 0? 1:-1;//updates the row multiplier with a positive or negative 1, to tell the shortest path finder which way to go
  60.         return((abs(cDiff)<abs(rDiff)));//if the vertical distance is more than the lateral distance, we should move vertically, otherwise move horizontally. Return true/false accordingly.
  61.         //return true if there is more vertical distance 
  62.     }
  63.  
  64.     float returnCellWeight(Cell weightedCell)//returns the weight/cost/length of moving into/through a cell
  65.     {
  66.         return(cellCost[weightedCell.m_Row][weightedCell.m_Col]);//literally just returns the value from the cellCost array, this is just used for convenience.
  67.     }
  68.  
  69.     float shortestRoute(Cell currCell)//this method ignores the costs and finds a direct route, it then returns the cost of that direct route TODO:add badCells avoidance for multi-round testing
  70.     {
  71.         Cell testCell = {currCell.m_Row,currCell.m_Col};
  72.         float moves=returnCellWeight(testCell);//set weight of moves to the weight of the new cell
  73.         //Setting moves = 0 alternatively makes riskier decisions that can have far better or far worse outcomes, keeping it as is will leave the results consistently better though.
  74.  
  75.         while((testCell.m_Col != finalCell.m_Col)||(testCell.m_Row != finalCell.m_Row))// While current cell and target cell aren't the same (when we haven't reached destination)
  76.         {
  77.             if(moveVert(testCell))//if we should move vertically (up and down rows)
  78.             {
  79.                testCell.m_Row+= rMult;// Move up or down rows, see rMult and cMult
  80.             }
  81.             else
  82.             {
  83.                 testCell.m_Col+= cMult;//otherwise move left and right through the columns
  84.             }
  85.             moves+=returnCellWeight(testCell);//add the weight of each move
  86.         }
  87.         return moves;//return weight of this attempt
  88.     }
  89.  
  90.  
  91.      Cell checkSurroundingCells(Cell curCell)/*This is closer to the brains, less of the meat and bones, this function checks the surrounding cells from the current cell, to see which has the cheapest possible route. I've set it like this to assume that the fastest route is generally going to be in the direction of the destination, with some deviation, in a much larger graph, the route could vary quite widely, but in a graph of this size generally curves gently towards a destination on the path of least resistance, if we run this multiple times, reduce the importance of seen cells, and increase the importance of blocked cells we should be able to find the absolutely fastest route, but it would increase the time to process*/
  92.     {
  93.         float smallestF;//this holds the smallest distance for comparison with current distance
  94.         float currentF;//this holds the current distance being compared
  95.         Cell smallestC;//this holds the cell to be selected for movement
  96.         if((curCell.m_Col > 0)||!(visited.seenCell(Cell{curCell.m_Row,curCell.m_Col-1},false)))//if the current cell isn't on the lowest column and the lower value hasn't been visited, check lower column value/
  97.         {
  98.             currentF = smallestF =shortestRoute(Cell{curCell.m_Row,curCell.m_Col-1});//set current and smallest f to weight of shortest route
  99.             smallestC = {curCell.m_Row,curCell.m_Col-1};//set Cell to current cell
  100.         }
  101.         if((curCell.m_Col < MAX_CELL-1)||!(visited.seenCell(Cell{curCell.m_Row,curCell.m_Col+1},false)))//make sure we aren't on the max column, same as above
  102.         {
  103.             currentF = /*returnCellWeight(Cell{curCell.m_Row,curCell.m_Col+1}, cellCost)+*/shortestRoute(Cell{curCell.m_Row,curCell.m_Col+1});//set current to weight of this route
  104.             if(currentF<smallestF)//if the current route is shorter, update
  105.             {
  106.                 smallestF=currentF;smallestC={curCell.m_Row,curCell.m_Col+1};//update the lowest weight and cell
  107.             }
  108.         }
  109.         if((curCell.m_Row > 0)||!(visited.seenCell(Cell{curCell.m_Row-1,curCell.m_Col},false)))//same as above, but with rows
  110.         {
  111.             currentF =shortestRoute(Cell{curCell.m_Row-1,curCell.m_Col});
  112.             if(currentF<smallestF)
  113.             {
  114.                 smallestF=currentF;smallestC={curCell.m_Row-1,curCell.m_Col};
  115.             }
  116.         }
  117.         if((curCell.m_Row < MAX_CELL-1)||!(visited.seenCell(Cell{curCell.m_Row+1,curCell.m_Col}, false)))
  118.         {
  119.             currentF =shortestRoute(Cell{curCell.m_Row+1,curCell.m_Col});
  120.             if(currentF<smallestF)
  121.             {
  122.                 smallestF=currentF;smallestC={curCell.m_Row+1,curCell.m_Col};
  123.             }
  124.  
  125.         }
  126.         if (visited.seenCell(smallestC,true)){/*badCells.seenCell(curCell,true);//TODO re-implement bad cells, check effects on time, still negative, return after final*/}
  127.         return smallestC;
  128.  
  129.     }
  130.  
  131.  
  132.     float avgWeight()//calculate average weight of cells
  133.     {
  134.         float totalCosts = 0.0F;
  135.         for(int i = 0; i < MAX_CELL; i++)// using MAX_CELL since it's already been established
  136.         {
  137.             for(int j = 0; j < MAX_CELL; j++)//for every cell in array, add weight
  138.             {
  139.                 totalCosts += cellCost[i][j];
  140.             }
  141.         }
  142.  
  143.         return (totalCosts / (MAX_CELL*MAX_CELL));//using MAX_CELL since it's already been established
  144.         // we return the average weight of all cells;
  145.     }
  146.  
  147.     public:
  148.     int findPath(Cell dest[], int maxDestLength, const Cell* startCell, const Cell* endCell, float cCost[MAX_CELL][MAX_CELL])
  149.     // findPath essentially just a copy of bestPath within scope of class. Could have just included it into this class, but wanted to built class entirely first. If bestPath fits better directly into the class for any reason, just change findPath name to bestPath
  150.     {
  151.         for (int g = 0; g < MAX_CELL; g++)
  152.         {
  153.             for (int h = 0; h < MAX_CELL; h++)
  154.             {
  155.                 cellCost[g][h] = cCost[g][h];
  156.             }
  157.         }
  158.         finalCell={endCell->m_Row, endCell->m_Col};
  159.         //cellCost = cCost;
  160.         int length = 0;
  161.         Cell workingCell = {startCell->m_Row, startCell->m_Col};
  162.         while ((workingCell.m_Row != endCell->m_Row) || (workingCell.m_Col != endCell->m_Col))
  163.         {
  164.             workingCell = checkSurroundingCells(workingCell);
  165.             final.seenCell(workingCell, true);
  166.         	length++;
  167.             //CostSoFar+=returnCellWeight(workingCell);
  168.             //ACTIVATE ABOVE LINE AND THE THREE COMMENTED BELOW TO CHECK PERFORMANCE
  169.         }
  170.         for(int i = 0; i < length; i++)
  171.         {
  172.             dest[i] = Cell{final.seenCells[i].m_Row,final.seenCells[i].m_Col};
  173.         }
  174.  
  175.  
  176.         //avgCost = avgWeight();            //ACTIVATE THESE THREE LINES
  177.         //cout << avgCost << endl;          // TO CHECK PERFORMANCE
  178.         //cout << CostSoFar/length << endl; // :)
  179.         return length;
  180.     }
  181.  
  182.  
  183. };
  184.  
  185. int bestPath(Cell dest[], int maxDestLength,
  186.                  const Cell* start, const Cell* end,
  187.                  float cellCost[MAX_CELL][MAX_CELL])
  188.     {
  189.         PathFindingForTest pFinder;
  190.  
  191.         return pFinder.findPath(dest, maxDestLength,start,end,cellCost);
  192.  
  193.         //TODO Add explicit garbage collection, just in case? Should be collected at end of scope of bestpath
  194.  
  195.     }
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202.  
  203.     int main()
  204. {
  205.     /* THIS IS JUST FOR TESTING ABOVE CLASS AND FUNCTIONS*/
  206.     /* Test in whatever methods suit you best, these were just the quick and dirty */
  207.  
  208.     srand(time(0));
  209.    const Cell sCell = {rand()%64,rand()%64};
  210.    const Cell eCell = {rand()%64,rand()%64};
  211.    float CellCost[64][64];
  212.         for(int i = 0; i < MAX_CELL; i++)
  213.         {
  214.             for(int j = 0; j < MAX_CELL; j++)
  215. 	    	{
  216. 	    		CellCost[i][j]=(float)(rand()%100);
  217. 	    	}
  218. 	    }
  219.         Cell dest[64];
  220.         int length = bestPath(dest, 64, &sCell, &eCell, CellCost);
  221.         cout << "There are " << length << " points between the starting point " << sCell.m_Row<<","<< sCell.m_Col << " and "  << eCell.m_Row<<","<< eCell.m_Col << " along this path" << endl;
  222.         for (int i = 0; i < length; i++)
  223.         {
  224.             cout << dest[i].m_Row << "," << dest[i].m_Col << endl;
  225.         }
  226.  
  227.    return 0;
  228. }
  229.  
  230.  
Success #stdin #stdout 0s 3432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
There are 19 points between the starting point 49,37 and 51,20 along this path
50,37
51,37
51,36
51,35
51,34
51,33
51,32
51,31
51,30
51,29
51,28
51,27
51,26
51,25
51,24
51,23
51,22
51,21
51,20
https://ideone.com/ECgv64
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!