designing seamless worlds?

[Stauricus]

hello everybody
today i'd like to ask how would you design a tiled seamless world?

i tried to create one, and so far it's working good.
i have a sf::View, and a slighter greater sf::Rect around it, so I only draw tiles that are inside the Rect before updating the View and drawing it to the screen. something like this:

void GameMap::drawMap(GameSys &game_sys_p){
    //get the drawArea (sf::Rect around the View)
    int mapX_min = game_sys_p.getDrawArea().left;
    int mapX_max = game_sys_p.getDrawArea().width;
    int mapY_min = game_sys_p.getDrawArea().top;
    int mapY_max = game_sys_p.getDrawArea().height;

    //search tiles inside the drawArea
    for (int mapX=mapX_min/32; mapX<mapX_max/32; mapX++){
        for (int mapY=mapY_min/32; mapY<mapY_max/32; mapY++){
            if (tiles_map[mapX][mapY].getType() == 1){
                sprite1.setPosition(mapX*32, mapY*32);
                game_sys_p.getGameWindow().draw(sprite1);
            }
        }
    }
}

but now i have to put characters in it. and this is a problem, since characters can walk almost on every pixel, and the tiles are drawn only at every 32 pixels. the only way i see to solve it is cycling trough ALL game characters and objects and checking it's positions every frame, to know if they are or not inside the drawArea. but i guess that it will make things too much slow. so i'm here asking the pros for any tips on that: how to optimize a seamless world? 
thanks in advance!

[Geheim]

I don't exactly get your question.
If you mean how to check if your characters can walk on the tiles, then why don't you just check the tiles near a character? You don't need to check EVERY tile, because you just need the ones near to the character

[Stauricus]

no, no, that's no the problem.
let's suppose the screen in centered at some random point, and we have 500 NPCs in the world map.
i'd like to know a way to check which NPCs need to be draw, but something smarter than cycling trough ALL npcs at every game frame, to know which are near the screen View (as this would consume too much CPU, i think).
is it clearer now?

[eXpl0it3r]

Welcome to the world of collision detection and other programming topics.
There's no general way to solve anything, but it really depends on what exactly you're creating. It starts with top-down vs side view, goes over jump'n'run vs turn-based and ends in what kind of collision detection you'd want.
So what exactly are you dreaming of?

[Geheim]

If a character is too far away from a certain point I would delete him and create him again if I am near to a certain point.
If you really want them to stay alive all the time you probably update them too, so a simple if checking if they are within the camera won't be the big deal then?

Where do you need 500 characters anyway? (just curious)

[Stauricus]

Welcome to the world of collision detection and other programming topics.
There's no general way to solve anything, but it really depends on what exactly you're creating. It starts with top-down vs side view, goes over jump'n'run vs turn-based and ends in what kind of collision detection you'd want.
So what exactly are you dreaming of?

i'm dreaming of something like this:


a top-down rpg, like the ones from RPG Maker. it has only one tile, i know. but of course i'm planning to add others later.
i don't think collision would be a problem when i can solve the little issue from this topic: how to tell SFML which NPCs should be drawn in a not-so-resource-expensive way in a seamless world?

If a character is too far away from a certain point I would delete him and create him again if I am near to a certain point.

ok, deleting him is no problem. but recreating would be. how to know exactly "here you should recreate this character"? that's my problem: check every frame for which NPC should be recreated? check all of inactive NPCs? not much advantage, i think

Where do you need 500 characters anyway? (just curious)

oh, to try to make a RPG city come alive hehe (without using some kind of crowd simulator, like the ones from gta)

[Geheim]

If you have 500 unique characters, which all should be somewhere specific and do their stuff, I don't think there is any better way of doing this. (maybe there is, but I don't know)
However if you have "random" characters, just to make a lively city, then you delete all characters which are too far (and maybe too long) away and create new ones after a (random) time or if you get near the city or something

[Stauricus]

um, ok, i just tought about something
what if i divide the world in "sections" (like big tiles), and each section store all the npcs in it's bounds? so, if the player is in a given section, i just loop trough the sections around him, checking the NPCs from it?
like this, i don't need to check all NPCs from the whole game. just the ones from neraly sections.

what you guys think about it?

[Nexus]

Spatial partitioning is exactly the optimization you need.

Sections are a good idea, you can experiment with the section size. In bigger worlds, a hierarchical approach can be appropriate; i.e. you divide the sections again. In this context, the quadtree data structure is an often-used technique.

[Stauricus]

yeah, i'll try this concept, and as soon as i have any results, i'll post it here
thanks everybody who's helping!