9 Replies - 1360 Views - Last Post: 07 August 2010 - 10:08 PM Rate Topic: -----

#1 R_aVe_N  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 07-August 10

Placement of increment statement

Posted 07 August 2010 - 08:30 PM

Ok I think I am just mind blocked from looking at code for the last few days, but my question is this in the method Graph_SearchAStar::Search(), I initialized the m_NumNodesVisited to zero and now i need to increment this variable everytime the PriorityQueue's insert method is called. For the life of me i can not figure out exactly were to place the increment statement so it will update as the PriortyQueue is called.




//-----------------------------------------------------------------------------
template <class graph_type, class heuristic>
void Graph_SearchAStar<graph_type, heuristic>::Search()
{
  m_NumNodesVisited = 0;
  //create an indexed priority queue of nodes. The nodes with the
  //lowest overall F cost (G+H) are positioned at the front.
  IndexedPriorityQLow<double> pq(m_FCosts, m_Graph.NumNodes());
  
  //put the source node on the queue
  pq.insert(m_iSource);

  //while the queue is not empty
  while(!pq.empty())
  {
    //get lowest cost node from the queue
    int NextClosestNode = pq.Pop();
	
    //move this node from the frontier to the spanning tree
    m_ShortestPathTree[NextClosestNode] = m_SearchFrontier[NextClosestNode];
	
    //if the target has been found exit
    if (NextClosestNode == m_iTarget) return;

    //now to test all the edges attached to this node
    graph_type::ConstEdgeIterator ConstEdgeItr(m_Graph, NextClosestNode);

    for (const Edge* pE=ConstEdgeItr.begin();
        !ConstEdgeItr.end(); 
         pE=ConstEdgeItr.next())
    {
      //calculate the heuristic cost from this node to the target (H)                       
      double HCost = heuristic::Calculate(m_Graph, m_iTarget, pE->To()); 

      //calculate the 'real' cost to this node from the source (G)
      double GCost = m_GCosts[NextClosestNode] + pE->Cost();

      //if the node has not been added to the frontier, add it and update
      //the G and F costs
      if (m_SearchFrontier[pE->To()] == NULL)
      {
        m_FCosts[pE->To()] = GCost + HCost;
        m_GCosts[pE->To()] = GCost;

        pq.insert(pE->To());

        m_SearchFrontier[pE->To()] = pE;
      }

      //if this node is already on the frontier but the cost to get here
      //is cheaper than has been found previously, update the node
      //costs and frontier accordingly.
      else if ((GCost < m_GCosts[pE->To()]) && (m_ShortestPathTree[pE->To()]==NULL))
      {
        m_FCosts[pE->To()] = GCost + HCost;
        m_GCosts[pE->To()] = GCost;

        pq.ChangePriority(pE->To());

        m_SearchFrontier[pE->To()] = pE;
      }
    }
  }
}


Is This A Good Question/Topic? 0
  • +

Replies To: Placement of increment statement

#2 Oler1s  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1395
  • View blog
  • Posts: 3,884
  • Joined: 04-June 09

Re: Placement of increment statement

Posted 07 August 2010 - 08:54 PM

Since a priority queue is not a function, but a data structure, I'm not sure what you mean by calling the priority queue...
Was This Post Helpful? 0
  • +
  • -

#3 R_aVe_N  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 07-August 10

Re: Placement of increment statement

Posted 07 August 2010 - 09:15 PM

Sorry if I wasn't to clear about this what I am trying to do is each time the program pulls a node from the priority queue the program will increment the m_NumNodesVisited by 1. This is only a small part of the overall code it is just were I am working now. What this program does is use A* to go through the nodes and find the fastest path to the target location. I am self taught so I try to learn all I can about programs.
Was This Post Helpful? 0
  • +
  • -

#4 Oler1s  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1395
  • View blog
  • Posts: 3,884
  • Joined: 04-June 09

Re: Placement of increment statement

Posted 07 August 2010 - 09:21 PM

And on what line of code is a node being pulled from the priority queue?
Was This Post Helpful? 0
  • +
  • -

#5 R_aVe_N  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 07-August 10

Re: Placement of increment statement

Posted 07 August 2010 - 09:35 PM

I believe it is pulled from this section of code, but I am no completely sure that is were I am having the problem

//get lowest cost node from the queue
	    int NextClosestNode = pq.Pop();


I was thinking that the statement should be placed after this section.
Was This Post Helpful? 0
  • +
  • -

#6 Oler1s  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1395
  • View blog
  • Posts: 3,884
  • Joined: 04-June 09

Re: Placement of increment statement

Posted 07 August 2010 - 09:40 PM

Quote

I was thinking that the statement should be placed after this section.
Sure. Logically, you can reason it out like this. If the above line of code is responsible for retrieving a node, and you want to increment a variable after retrieving a node, then it follows that that line of code to increment a variable should come after this line...

This post has been edited by Oler1s: 07 August 2010 - 09:40 PM

Was This Post Helpful? 0
  • +
  • -

#7 R_aVe_N  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 07-August 10

Re: Placement of increment statement

Posted 07 August 2010 - 09:46 PM

lol thank you for not flat out telling, but making me find it myself. I think I am biting off more than I can chew doing this program, but I wanted to challenge myself to learn more. I know that it might of sounded like a stupid question to people that know a lot about C++, but sometimes for people like me I need a little extra kick in the pants to push us in the right direction. Thanks again :rockon:
Was This Post Helpful? 0
  • +
  • -

#8 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Placement of increment statement

Posted 07 August 2010 - 09:50 PM

for future reference when you think something should go somewhere, just put it there and try it.

This post has been edited by ishkabible: 07 August 2010 - 09:51 PM

Was This Post Helpful? 0
  • +
  • -

#9 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Placement of increment statement

Posted 07 August 2010 - 10:03 PM

this is strange i found the book this came out off and it dose not increment this variable, with what purpose is this being used?

This post has been edited by ishkabible: 07 August 2010 - 10:04 PM

Was This Post Helpful? 0
  • +
  • -

#10 Oler1s  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1395
  • View blog
  • Posts: 3,884
  • Joined: 04-June 09

Re: Placement of increment statement

Posted 07 August 2010 - 10:08 PM

Quote

I think I am biting off more than I can chew doing this program,
You are.

Quote

but I wanted to challenge myself to learn more
There is a difference between challenging yourself and putting yourself in an impossible position. A challenge is something you can solve on your own efforts, with enough perseverence and exertion. Is this program something that falls under a challenge? Really? Does it?

Quote

I know that it might of sounded like a stupid question to people that know a lot about C++,
You misunderstand. You think you should be ashamed about your lack of knowledge and experience. On the contrary, you should be very forthcoming about what you don't know. What you should demonstrate however, is good sensibility and logical approach.

Struggling with incrementing a variable is not a good sign, when you are dealing with game AI. Yeah, that code was copied verbatim from Programming Game AI by Example. You can't just read your way to competence. You need to gain experience actually programming.

By all means, do what you enjoy. But do understand that reading does not equate to programming competence. Knowing things, does not make a good programmer.

This post has been edited by Oler1s: 07 August 2010 - 10:11 PM

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1