C++

Forum

 
 
A leak I can't find

Apr 17, 2013 at 10:16am
Jonas Wingren (108)
Hi!
I'm writing a map generator for a game that uses a hexgrid.
At the moment I'm just trying to make continents but I've been having some issues.

The current problem is that somehow more hexagons are added then exists on the map. I don't know why it happens but I can tell you a little about my generation code:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
  /*picks a random seed, if it randoms to water set all ungenerated neighbours
 to water else add ungenerated neighbours to the m_ActiveSeeds and repeat until empty */
void Map::generateCrude(){
//mod >1 increases chance for water
    int mod = 1;
//shuffle it to get a random element
    random_shuffle(m_ActiveSeeds.begin(), m_ActiveSeeds.end());
    pair<int,int> ID = m_ActiveSeeds.front()->getID();
//to steer the generation away from complete randomness
    if(getTypeNeighbours("land", ID.first, ID.second) > 3) mod = 0.9;
    if(getTypeNeighbours("water", ID.first, ID.second) > 3) mod = 1.2;
    string type = randomType(mod);
    cout << m_ActiveSeeds.size() << endl;
    m_ActiveSeeds.front()->setTerrain(type,1);
    vector<Block*> temp = getAllNeighbours(ID.first, ID.second);
    if(type == "water"){
        do{
            // if it's already generated
            if(temp.front()->terrainExists("land") || temp.front()->terrainExists("water") ){
                temp.erase(temp.begin());
            }
            else{
                //set to water and if it exists in the m_ActiveSeeds remove it from there
                temp.front()->setTerrain("water", 1);
                for(std::vector<Block*>::iterator it = m_ActiveSeeds.begin();it != m_ActiveSeeds.end();it++){
                    if(checkSameID(temp.front(), *it)){
                        m_ActiveSeeds.erase(it);
                        break;
                    }
                }
                temp.erase(temp.begin());
            }
        }while(temp.empty() == false);
    }
    else{
        //else just check if the neighbours exists in the list otherwise add them.
        for(int i = 0; i < temp.size();i++){
            addSeed(temp.at(i));
        }
    }
    //remove the used element
    m_ActiveSeeds.erase(m_ActiveSeeds.begin());
    return;
}


I've been through my program many times in the past few days but I can't find it.

And also it generates perculiar maps... it's like it's split in two from the middle and generates the same thing on both sides...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
                                                  
                                      W     W     
             W     W                 WWW   WWW    
            WWW   WWW                W#W  WW#WWW  
            W#W  WW#WWW             WW#W #W###WWWW
           WW#W #W###WWWW           WWW#W########W
           WWW#W########W           W####WW#######
           W####WW#######          W##############
          W##############         WW##############
         WW##############        WW###############
        WW###############W       WW###WW##########
W       WW###WW###########W       WWW#############
#W       WWW##############WW      WWW#############
#WW      WWW###############WW      WWW############
##WW      WWW#############W#WW      WWW###########
#W#WW      WWW###########WWWWW      WW############
WWWWW      WW############WWW       WW#############
WWW       WW#############          W##############
          W##############         WW####W#########
         WW####W#########         W##############W
         W##############W         WWW###W#########
         WWW###W#########         WWW#######W#####
         WWW#######W#####          ###############
          ###############         W##W####W##W####


I've upload the rest of the code to this location: https://www.dropbox.com/s/jzp0yuqw0c835r1/MapGen.7z?v=0mcn

You should change the path in the Map::saveCurrentMAP function
Last edited on Apr 17, 2013 at 10:20am
Apr 17, 2013 at 10:45am
Catfish3 (666)
25
26
27
28
29
30
 
                for(std::vector<Block*>::iterator it = m_ActiveSeeds.begin();it != m_ActiveSeeds.end();it++){
                    if(checkSameID(temp.front(), *it)){
                        m_ActiveSeeds.erase(it);
                        break;
                    }
                }


I see the classic mistake of changing the vector's contents, while iterating over them. Same mistake can be done with vector::insert() as well.

http://cplusplus.com/reference/vector/vector/erase/#validity

Iterator validity

Iterators, pointers and references pointing to position (or first) and beyond are invalidated, with all iterators, pointers and references to elements before position (or first) are guaranteed to keep referring to the same elements they were referring to before the call.


Edit: I suggest you use std::remove_if():
http://cplusplus.com/reference/algorithm/remove_if/
Last edited on Apr 17, 2013 at 10:49am
Apr 17, 2013 at 11:10am
Jonas Wingren (108)
I don't go back after I've found a matching object, because there can only be one matching object maximum. So I'm guessing pointer validity isn't a problem-

But I can't get remove_if() to work.

And what do you mean by changing? yes, I remove an element, but when I have I break the loop.
Last edited on Apr 17, 2013 at 11:15am
Apr 17, 2013 at 1:20pm
Catfish3 (666)
And what do you mean by changing? yes, I remove an element, but when I have I break the loop.

I totally ignored the break; so I guess my previous post was wrong.
Apr 17, 2013 at 2:40pm
Jonas Wingren (108)
I thought you found something that was wrong and would fix the problem :(.
Apr 17, 2013 at 7:09pm
Jonas Wingren (108)
any ideas where things might go wrong?
Apr 17, 2013 at 10:03pm
Jonas Wingren (108)
Because I've been over this code for three days without finding the problem that's causing the logic error.

But it's one of these:
1.A problem getting the correct neighbours.

2. A problem with checking if the pointer that's added already exists.

3. A problem removing a pointer if it's generated, in the event that a water neighbour is in the seed list.


But as I said, long time, a lot of staring... and no solution.
Last edited on Apr 17, 2013 at 10:03pm
Apr 18, 2013 at 1:42am
Jonas Wingren (108)
Going to bed, would love if someone looked at the code and found the problem.
Apr 18, 2013 at 10:23am
Jonas Wingren (108)
I'm going mad here, is there someway to find this problem? I'll keep looking at it today but then I'll probably just rewrite the entire thing to save time -.-.

I've added lots of safeguards to make sure that the check if it already exists works, and it appear to be doing that.

There appear to be nothing wrong with the ID system, all pointers inside the m_ActiveSeeds have allowed IDs.

And it appear to be removing the correct amount of pointers as it should.
Last edited on Apr 18, 2013 at 10:50am
Apr 18, 2013 at 10:36am
writetonsharma (1461)
I am not able to open the link.

I wan to compile and run this function with minimum interaction with rest of the code. Just looking at it might not be enough.
Apr 18, 2013 at 11:01am
Jonas Wingren (108)
You can't open the link, or you can't open the file?

The file is a rar file.
But if it's the link I don't know what's wrong...

My friend can open the link and so can I.
Last edited on Apr 18, 2013 at 11:06am
Apr 18, 2013 at 11:23am
writetonsharma (1461)
The link.
Apr 18, 2013 at 11:25am
Jonas Wingren (108)
Apr 18, 2013 at 2:17pm
writetonsharma (1461)
What do you think about your getAllNeighbours().

If I change it to this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
vector<Block*> Map::getAllNeighbours(int x, int y){
    Block *p;
    vector<Block*> Neighbours;
    if(mapyModulos(y+1, Y_COUNT) != - 1){
        p = &m_Map[mapxModulos(x, X_COUNT)][y + 1];
        Neighbours.push_back(p);
        //p = &m_Map[mapxModulos(x + 1, X_COUNT)][y + 1];
        //Neighbours.push_back(p);
    }
    if(mapyModulos(y -1, Y_COUNT) != -1){
        p = &m_Map[mapxModulos(x, X_COUNT)][y - 1];
        Neighbours.push_back(p);
        //p = &m_Map[mapxModulos(x+1, X_COUNT)][y - 1];
        //Neighbours.push_back(p);
    }
    p = &m_Map[mapxModulos(x - 1, X_COUNT)][y];
    Neighbours.push_back(p);
    p = &m_Map[mapxModulos(x + 1, X_COUNT)][y];
    Neighbours.push_back(p);

	/*****************************/
// 	p = &m_Map[mapxModulos(x - 1, X_COUNT)][y-1];
// 	Neighbours.push_back(p);
// 	p = &m_Map[mapxModulos(x - 1, X_COUNT)][y + 1];
// 	Neighbours.push_back(p);
    return Neighbours;
}


will this work ?
Apr 18, 2013 at 2:20pm
writetonsharma (1461)
I get this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
                                                  
                                      W           
             W                      WWWW          
           WWWW                    WWW#WW         
          WWW#WW                  WW###W          
         WW###W                    WWWWW          
          WWWWW                     W W           
           W W                                    
                                        W         
               W                       WWW        
              WWW                     WW#WW       
             WW#WW                    WW#WWW  W   
             WW#WWW  W   W           WW####WWWWWWW
W           WW####WWWWWWWWW           WW#####W##WW
WW           WW#####W##WW#WW          WW###WWWW#W#
#WW          WW###WWWW#W#WW            WWW#WWWW###
WW            WWW#WWWW###W              WWWW WW###
W              WWWW WW###                 W   WWWW
                 W   WWWW                      WWW
                      WWW


PS: I did couple of more small changes, just removed warnings where you are assigning a double to an int.
1
2
 
mod = 0.9;
mod = 1.2;
Last edited on Apr 18, 2013 at 2:22pm
Apr 18, 2013 at 5:19pm
Jonas Wingren (108)
No it won't work since the map I'm creating is a hexgrid not a square grid. http://www.wuphonsreach.org/Games/Civ5/HexGrid-Civ5-Hexagons-24x24.png


I'm not sure why that fixed the problem though. Must be that it now adds less then normally and therefor runs out of stuff to generate much faster, it also messes up the water generation since now the chance of water has greater chance / tile to occur.

So, I'm generating a hexmap, not a square one, so that won't do. I'm just using the textfile as a temporary solution until I fixed the first parts of this function, after that I'll make some SDL or SFML interface. Not sure which yet.

found one problem though:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
vector<Block*> Map::getAllNeighbours(int x, int y){
    Block *p;
    vector<Block*> Neighbours;
    if(mapyModulos(y+1, Y_COUNT) != - 1){
        p = &m_Map[mapxModulos(x, X_COUNT)][mapyModulos(y + 1, Y_COUNT)]; //before this could be Y_COUNT which would try to access an element outside. Still same problem though.
        Neighbours.push_back(p);
        p = &m_Map[mapxModulos(x + 1, X_COUNT)][mapyModulos(y + 1, Y_COUNT)];
        Neighbours.push_back(p);
    }
    if(mapyModulos(y -1, Y_COUNT) != -1){
        p = &m_Map[mapxModulos(x, X_COUNT)][mapyModulos(y - 1, Y_COUNT)];
        Neighbours.push_back(p);
        p = &m_Map[mapxModulos(x+1, X_COUNT)][mapyModulos(y - 1, Y_COUNT)];
        Neighbours.push_back(p);
    }
    p = &m_Map[mapxModulos(x - 1, X_COUNT)][mapyModulos(y, Y_COUNT)];
    Neighbours.push_back(p);
    p = &m_Map[mapxModulos(x + 1, X_COUNT)][mapyModulos(y, Y_COUNT)];
    Neighbours.push_back(p);
    return Neighbours;
}



Still same problem...

Didn't even realize the int problem Even though I played around with the numbers and saw no difference, should have realized.

I get this atm:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
           W                      WWWWWW          
         WWWWWW                 WWWW##WWW         
       WWWW##WWW               WW##W####WW        
      WW##W####WW              WW########WWW      
      WW########WWW          W WWWW######WWWW     
    W WWWW######WWWW      WWWWWW############W     
 WWWWWW############W      WW#############W##WW    
 WW#############W##WW     ##################WW    
 ##################WW     W##WW############WWW W  
 W##WW############WWW W   WWWW##W############WWWW 
 WWWW##W############WWWW     W#######WW#########WW
    W#######WW#########WW   WW#################WWW
   WW#################WWW   W##WW###########W##WW#
   W##WW###########W##WW# W #WWW##WWWW#########WWW
 W #WWW##WWWW#########WWW#W# WWWWWWWWW#W##########
#W# WWWWWWWWW#W########## #WW WWWWW###W#########WW
 #WW WWWWW###W#########WW WWW    WW###############
 WWW    WW###############       WW################
       WW################       WW##############W#
       WW##############W#      WW#################
      WW#################      WWW################
      WWW################      WWWW###############
      WWWW###############       WW#####WW#########
       WW#####WW#########       WW#W##############
       WW#W##############      WW####W############


No clue what's causing the copy like behavior or the straight lines...
Last edited on Apr 18, 2013 at 5:42pm
Apr 18, 2013 at 5:43pm
writetonsharma (1461)
Did you look at the warnings where you are assigning double to int ?

I will have to understand your problem a little more to help you. You can explain more if you have anything left. I will look at it tomorrow.

Edit: I want to understand what is expected and what is actually coming.
Last edited on Apr 18, 2013 at 5:46pm
Apr 18, 2013 at 6:31pm
Jonas Wingren (108)
Ok. Let's take this from the beginning.

I'm creating a generator to a game.

each block of the map is a hex and the world is cylindrical meaning that you can walk from the far left edge to the far right (in a step, you know what I mean).

I place a number of land spots on the map. Called seeds.

I then remove these land blocks from the list with "active seeds" simply stuff that can be generated next. and add their neighbours to that list.

I then, for the rest of the process:
1. shuffle the list.
2. Choose what it randoms to.
3. If it randoms to land then remove that seed from the list and add it's neighbours if the neighbours are not on the list.... and not already generated. Hold on might found the problem here...
Last edited on Apr 18, 2013 at 6:35pm
Apr 18, 2013 at 6:45pm
Jonas Wingren (108)
Changed the Map::addSeed function so that it checks that the block isn't already generated. But now it won't generate at all, it just places the initial seeds.

brb an hour or so. btw changed the randomPlace function so that it uses push_back instead of addSeed since they are already generated when I add them.



1
2
3
4
5
6
7
8
9
10
11
12
 
bool Map::addSeed(Block* test){
    for(int i = 0; i < m_ActiveSeeds.size(); i++){
        if(checkSameID(test, m_ActiveSeeds.at(i))){
            return false;
        }
        if(m_ActiveSeeds.at(i)->terrainExists("land") || m_ActiveSeeds.at(i)->terrainExists("water")){
            return false;
        }
    }
    m_ActiveSeeds.push_back(test);
    return true;
}



Nvm fixed it after looking at it for 10 seconds :)
it's test-> not m_ActiveSeeds

Thanks all who tried to help :).
Last edited on Apr 18, 2013 at 7:28pm
Topic archived. No new replies allowed.