spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

C-/C++-Quelltext

            //regular a-star
            while(!open.empty())
            {
                opened current = open.front();
                open.pop_front();

                size_t c_index = this->getindex(current.x,current.y);
                float current_height = heights[c_index];

                //expandNode(current)
                for(int counter = 0; counter < 6; counter++)
                {
                    int n_x         = current.x + (current.y%2 ? neighbours_odd : neighbours_even)[counter][0];
                    int n_y         = current.y + (current.y%2 ? neighbours_odd : neighbours_even)[counter][1];
                    
                    if(0 <= n_x && n_x < grid_width && 0 <= n_y && n_y < grid_height)
                    {
                        size_t n_index  = getindex(n_x,n_y);

                        if(!closed[n_index])
                        {
                            float h_diff = heights[n_index] - current_height;
                            Val tentative_g = static_cast<Val>(values[c_index] + sqrt(1+h_diff*h_diff));//cost to every closest neighbor is 1 in a hex-grid

                            if(this->infinit[n_index] || tentative_g < this->values[n_index])
                            {
                                this->infinit[n_index]  = false;
                                this->values[n_index]   = tentative_g;
                                opened val(n_x,n_y,tentative_g+get_approx_cost(n_x,n_y,n_index,x,y,startindex));

                                bool inserted = false;
                                typename std::list<opened>::iterator it = open.begin();
                                while(it != open.end())
                                {
                                    if(it->x == n_x && it->y == n_y)
                                        it = open.erase(it);
                                    else
                                    {
                                        if(!inserted && val.approx_cost < it->approx_cost)
                                        {
                                            inserted = true;
                                            it = open.insert(it, val);
                                        }
                                        ++it;
                                    }
                                }
                                if(!inserted)   open.push_back(val);
                            }
                        }
                    }
                }
                closed[c_index] = true;

                if(current.x == ret.first && current.y == ret.second)
                    break;
            }