Game Development Megathread

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Game Development Megathread

«‹›623 »

That Turkey Story: Mar 30, 2003

mewse posted:

Hell no. What do you gain by looping faster than 60 Hz on an LCD?

Not that I'm necessarily advocating it, but constantly looping does not mean that you are rendering in every iteration of the game loop. You usually have limits for lots of things -- how often physics are updated, how often sound locations are updated, how often you render, etc. Each component may be updated at different rates. Believe it or not, many games really do just eat up the CPU like this and that doesn't mean they are trying to render 1000 frames per second.

# ? Apr 5, 2012 04:26

Adbot: ADBOT LOVES YOU

# ? May 25, 2024 19:07

mewse: May 2, 2006

That Turkey Story posted:

Not that I'm necessarily advocating it, but constantly looping does not mean that you are rendering in every iteration of the game loop. You usually have limits for lots of things -- how often physics are updated, how often sound locations are updated, how often you render, etc. Each component may be updated at different rates. Believe it or not, many games really do just eat up the CPU like this and that doesn't mean they are trying to render 1000 frames per second.

I realize game loops can be decoupled from screen refresh. What do you gain by your game loop going faster than 60 Hz.

# ? Apr 5, 2012 04:28

xgalaxy: Jan 27, 2004; i write code

Every professional game engine I've worked with has utilized 100% CPU.
There were only very rare cases where you were intentionally sleeping the main thread.

xgalaxy fucked around with this message at 04:42 on Apr 5, 2012

# ? Apr 5, 2012 04:29

That Turkey Story: Mar 30, 2003

mewse posted:

I realize game loops can be decoupled from screen refresh. What do you gain by your game loop going faster than 60 Hz.

You may wish for other components to go faster, for instance, physics or even just game logic.

# ? Apr 5, 2012 04:34

mewse: May 2, 2006

That Turkey Story posted:

You may wish for other components to go faster, for instance, physics or even just game logic.

For zero benefit

# ? Apr 5, 2012 04:37

That Turkey Story: Mar 30, 2003

mewse posted:

For zero benefit

No, not really. Just because you don't see the effects of things like physics every frame doesn't mean that they are not important. For example, depending on how often you update physics and how you interpolate movement can mean the difference between whether you are able to jump up onto a given platform or not.

# ? Apr 5, 2012 04:40

Unormal: Nov 16, 2004; Mod sass? This evening?! But the cakes aren't ready! THE CAKES!; Fun Shoe

mewse posted:

For zero benefit

You could get benefit out of running portions of a planning AI at 100%, or streaming resources in and out of memory, or running threads or pseudothreads doing things like updating shadow maps or geometry that don't happen every frame, but get benefit out of going on asap.

# ? Apr 5, 2012 04:41

xgalaxy: Jan 27, 2004; i write code

For clarification. If the game isn't threaded or whatever, then obviously you would only be utilizing that one core. So on a dual core, for example this would show up as 50% CPU usage. And then, if you are using multiple cores, then how effectively you are distributing work load across them will determine whatever spikes and slumps in CPU percent utilized.

I guess I just don't see a compelling reason to purposely sleep the main thread, especially when sleep, on windows in particular, is notoriously inaccurate and is not guaranteed to sleep for the length requested -- usually it takes longer. So when you have very specific Hz budgets for rendering, physics, etc, relying on sleep is a very bad idea.

# ? Apr 5, 2012 04:42

mewse: May 2, 2006

That Turkey Story posted:

No, not really. Just because you don't see the effects of things like physics every frame doesn't mean that they are not important. For example, depending on how often you update physics and how you interpolate movement can mean the difference between whether you are able to jump up onto a given platform or not.

So you want a faster game loop so the player CAN jump on the platform, or so that they CAN'T jump on the platform?

Doom 3 capped at 60 Hz because players were deliberately setting the Q3A tick rate at a certain breakpoint to jump higher.

Unormal posted:

You could get benefit out of running portions of a planning AI at 100%, or streaming resources in and out of memory, or running threads or pseudothreads doing things like updating shadow maps or geometry that don't happen every frame, but get benefit out of going on asap.

This actually does make sense since it's variable processing time features that you can throw the CPU at. Eating up the CPU because you think "faster game loop = better" is stupid

# ? Apr 5, 2012 04:48

xgalaxy: Jan 27, 2004; i write code

Quake, doom, etc. cap simulation at 60hz.
Theyre still running the main loop.

Just because you're capping at whatever Hz doesn't mean you stop looping, ever.
And drat straight they're trying to render as fast as possible.

# ? Apr 5, 2012 04:54

Pfhreak: Jan 30, 2004; Frog Blast The Vent Core!

mewse posted:

This actually does make sense since it's variable processing time features that you can throw the CPU at. Eating up the CPU because you think "faster game loop = better" is stupid

Especially if you have the game paused but still open. That drives me nuts. If I want to go check an FAQ while I'm gaming, I expect the game to all but halt while I do so.

# ? Apr 5, 2012 05:37

Unormal: Nov 16, 2004; Mod sass? This evening?! But the cakes aren't ready! THE CAKES!; Fun Shoe

It is pretty typical, even for games that are balls-out when running, to watch window state and yield a bunch of CPU when minimized.

# ? Apr 5, 2012 05:45

xgalaxy: Jan 27, 2004; i write code

Unormal posted:

It is pretty typical, even for games that are balls-out when running, to watch window state and yield a bunch of CPU when minimized.

Yes, exactly. Nothing wrong with that, and pretty common.

# ? Apr 5, 2012 05:59

SupSuper: Apr 8, 2009; At the Heart of the city is an Alien horror, so vile and so powerful that not even death can claim it.

Thanks for all the feedback. It's good to know that I'm in the right direction, but a bit scary that this is considered the right direction. :v:

OneEightHundred posted:

100% CPU usage in a real-time game is not exactly a problem, your game will chew up every ounce of CPU it has available unless it (or something it calls) tells the OS that it doesn't need the CPU for a while or until something happens. Delay is not a "hack," it's one of the "I don't need this CPU" mechanisms and a process that doesn't take long to do things between delays will take up negligible amounts of CPU. Alternately, use event responses and timers from the windowing API instead and don't even have a main loop.

Well what little I've read does consider it a hack, because the proper way is to figure out what CPU I need when I need it, and I should just hook stuff to when stuff happens (SDL_PollEvent vs SDL_WaitEvent), and only react when stuff needs reacting, and etc. The problem is just figuring out when my game is just paused / running timers / processing stuff / etc is really complex and I wouldn't even know where to begin to do these changes.

Locked framerate is another choice, though I enjoy watching the FPS counter reach thousands.

OneEightHundred posted:

Re: Resource management, that's a classic case of an application-specific answer. The goal of resource management is three-fold:
- Don't run out of allocation space
- Try to have anything the user might experience loaded before they experience it
- Failing the previous point, make the replacement experience as non-annoying as possible

If you can load everything you'd need for a level into memory before the level starts, you win on all 3 counts, but failing that, the usual solutions are:
- Drop resources if you can determine that you don't need them any time soon or at all (i.e. one-time sound/video clips that have finished playing, old levels, resources not used on the current level)
- Preload as much as you can get away with.
- If the user reaches something that needs a load, use a placeholder or stall the game until it finishes loading.

Again, the problem here is my game isn't some simple level-based affair where I can easily guess what resources will be required in the future, and just taking the opposite approach of loading-stuff-as-needed is probably just as bad.

I've had a possibly-smarter resource management idea for a while, but I can't figure out if it's any good or not until I put it in practice, which will be a long time since making the game part of the game takes priority.

Kelson posted:

I vehemently disagree, as would most professional ~~game~~ developers. Only do those things YOU are talented at or require (and/or interested in for hobbyists).

Can I write a graphics engine? Sure, but I want to make a game, not a graphics engine. Developing a graphics engine, audio engine, physics engine, XML library, etc etc etc all delay (if not preempt) the game. They're fascinating and deep topics, no question, but they're means to an end - not the end themselves.

That's true everywhere. Minimize reinventing wheels. Ford could innovate a new production technique for each wheel on each car model. The standard wheel + custom hubcap works well enough though. When it doesn't, then innovate on that component.

I completely agree. I'm not saying you have to make every game from complete scratch, if you can find engines and libraries that cover all your needs, go for it. But every game is completely different, and more often than not you'll want it to do something that no engine will, so you have to at least know all these things so you can always do what you want your game to do when the need arises, not just submit to the engine's will. I imagine this is why most professional developers end up growing their own in-house engines.

For example, OpenXcom needs to be a 2D 8-bit low-res game that reproduces the look and feel of an old DOS game and handles non-standard resource formats and etc. Where are you gonna find an engine that covers all that? I got SDL to keep me company and that's about it.

xgalaxy posted:

I don't get the CPU thing.
A game, by it's very nature, is a tight loop.
It's supposed to use 100% CPU.

Try telling that to people who will argue that something that looks like a 20-year old game should work like a 20-year-old game and all these other completely different games they have don't use 100% CPU and :v:

(I see their point but I can't make Game A work like Game B or Game C just because they want it to, even if the whole goal of OpenXcom is to make Game A work like Game B).

mewse posted:

Hell no. What do you gain by looping faster than 60 Hz on an LCD?

Presumably your game is not just concerned with rendering and you'll want it to process all the physics/AI/gameplay/logic stuff before the next render cycle hits so you don't stutter.

SupSuper fucked around with this message at 13:18 on Apr 5, 2012

# ? Apr 5, 2012 13:16

Bruegels Fuckbooks: Sep 14, 2004; Now, listen - I know the two of you are very different from each other in a lot of ways, but you have to understand that as far as Grandpa's concerned, you're both pieces of shit! Yeah. I can prove it mathematically.

xgalaxy posted:

I guess I just don't see a compelling reason to purposely sleep the main thread, especially when sleep, on windows in particular, is notoriously inaccurate and is not guaranteed to sleep for the length requested -- usually it takes longer. So when you have very specific Hz budgets for rendering, physics, etc, relying on sleep is a very bad idea.

I'm not sure 'inaccurate' is the right way to put it. The windows clock is only accurate to a certain number of milliseconds, depending on platform - 15.6 is a common number, but the definition of what a tick is can vary even across windows platform. And the definition of sleep on win32 is more along the lines of "block the thread for x millseconds" - after that, the thread is put in the ready state, but it's up to the OS when it's actually going to resume.

If you have to do something extremely sensitive/time-based using the win32 api, you're better off using queryperformancecounter if you just need to get the time - but queryperformancecounter doesn't have a notification mechanism, so it isn't straightforward to use it as a timer, so you should be using a multimedia timer for that. This generalizes to other platforms in that it's a really good idea to figure out what the timer resolution and other idiosyncrasies of threading are going to be, otherwise if you dealing with a problem where something got 4 milliseconds slower and it's screwing performance (user complains the scrolling got slower! 10 million dollar contract at risk), you're going to have problems.

A sleep is never a good solution to a problem - it might work, but you're always better off if you do the research to figure out how to understand when something is supposed to kick in, rather than waiting for a arbitrary amount of time.

# ? Apr 5, 2012 14:22

OneEightHundred: Feb 28, 2008; Soon, we will be unstoppable!

SupSuper posted:

Again, the problem here is my game isn't some simple level-based affair where I can easily guess what resources will be required in the future, and just taking the opposite approach of loading-stuff-as-needed is probably just as bad.

I've had a possibly-smarter resource management idea for a while, but I can't figure out if it's any good or not until I put it in practice, which will be a long time since making the game part of the game takes priority.

What's relevant can depend on what visible. If you see a certain type of enemy, then you might want to load (or at least start loading) any animations or sounds that enemy might play. The region you're in might determine what enemies and environment assets need to be loaded.

I think that, generally, the best strategy is to stream in what you think you'll need soon, give priority to things you need immediately (and possibly wait on it), and put everything not in the relevant set into an elimination queue which you can use to eliminate resources as you run out of room.

# ? Apr 5, 2012 15:43

Gold Dust Gasoline: Jul 11, 2006; just be yourself and you'll be fine; Pillbug

You can also do what the unreal engine does and keep the lowest detail mip map of textures always around to use as temporaries while you load the full rez ones.

Same with lowest lod of models, but you can't really do that with animations.

This is all assuming your game is completely random with no way to guess what resources you might need intelligently.

# ? Apr 5, 2012 15:54

Rupert Buttermilk: Apr 15, 2007; 🚣RowboatMan: ❄️Freezing time🕰️ is an old P.I. 🥧trick...

Quick question: Does Flixel/Stencyl do parallaxing for 2D platformers?

# ? Apr 5, 2012 16:03

Centripetal Horse: Nov 22, 2009; Fuck money, get GBS

This could have bought you a half a tank of gas, lmfao -
Love, gromdul

Rupert Buttermilk posted:

Quick question: Does Flixel/Stencyl do parallaxing for 2D platformers?

Sure, to a degree. Stencyl makes parallax scrolling fairly easy, as long as you have pre-rendered backgrounds to work with. All you need do, in that case, is load the backgrounds, arrange their z-order, and set their scroll speed percentages.

However, Stencyl does not provide a way to use multiple tilemap layers in a parallax scrolling scheme. There is a parallax behavior on the Forge, but I don't know anything about it.

# ? Apr 5, 2012 17:25

Shalinor: Jun 10, 2002; _{Can I buy you a rootbeer?}

Centripetal Horse posted:

Sure, to a degree. Stencyl makes parallax scrolling fairly easy, as long as you have pre-rendered backgrounds to work with. All you need do, in that case, is load the backgrounds, arrange their z-order, and set their scroll speed percentages.

However, Stencyl does not provide a way to use multiple tilemap layers in a parallax scrolling scheme. There is a parallax behavior on the Forge, but I don't know anything about it.

Doesn't DAME somehow handle the multiple parallaxing tile layers? I'm pretty sure it lets you create any number of tile-based layers with independent parallax, and I thought you could dump basically any DAME level directly into Flixel?

# ? Apr 5, 2012 17:30

Hughlander: May 11, 2005

Are there any papers or GDC talks on security in a Freemium game? I'm starting to think about ways of authenticating/validating unlocks/purchases but would like to read/watch anything that's already public...

# ? Apr 5, 2012 19:34

OneEightHundred: Feb 28, 2008; Soon, we will be unstoppable!

Most freemium games run the actual game on hosted servers in which case it's as trivial as requiring a registered account to play and only allowing unlocked items to be used.

Games run on private servers (i.e. TF2, BF Heroes) generally rely on servers being compliant and doing the same thing, but have to concede modded servers being able to get around it eventually and the most you can do is delist them.

Authentication usually just use a client-server public key encryption scheme and password hashing. Basically:
- Client generates a random symmetric (i.e. AES, Blowfish) encryption key
- Client encrypts the key using a public key encryption algorithm (i.e. ECC, RSA)
- Client sends that encrypted key to the server as part of the initial handshake
- Server decrypts the key using its private key and all further communication occurs under the symmetric cipher
- Client sends password hash (i.e. SHA2) to the server
- Server compares the password hash against the hash in its database
- If it matches, great, user is considered logged in

OneEightHundred fucked around with this message at 19:47 on Apr 5, 2012

# ? Apr 5, 2012 19:40

Centripetal Horse: Nov 22, 2009; Fuck money, get GBS

This could have bought you a half a tank of gas, lmfao -
Love, gromdul

Shalinor posted:

Doesn't DAME somehow handle the multiple parallaxing tile layers? I'm pretty sure it lets you create any number of tile-based layers with independent parallax, and I thought you could dump basically any DAME level directly into Flixel?

I geared my response toward Stencyl more than Flixel. Stencyl uses Flixel, but there are several levels between Stencyl and Flixel, which sometimes makes it difficult to dump raw code into the right place. I have not tried a DAME map with Stencyl, but it might work.

# ? Apr 5, 2012 21:01

Hughlander: May 11, 2005

OneEightHundred posted:

Most freemium games run the actual game on hosted servers in which case it's as trivial as requiring a registered account to play and only allowing unlocked items to be used.

Games run on private servers (i.e. TF2, BF Heroes) generally rely on servers being compliant and doing the same thing, but have to concede modded servers being able to get around it eventually and the most you can do is delist them.

I haven't played Battlefield Heroes yet, but what I mean specifically is what is the security around the generation of Valor Points on a private server? What's to stop me from running a private server and reporting the generation of Valor points through completing missions? Or to have a script running 24/7 that every 60 minutes I gained 60 valor points or whatever the expected 'average' amount of points per unit of time is? If there's a reward for doing a specific mission, what's to stop someone from saying they did that mission on a private server, etc...

My concern is when not playing on a hosted server a player claims to have gotten an unlock that could normally cost a micropayment but is also available through player action (Completing a challenge/mission, spending xp/Valor points/Unlock points, etc...) and hacking that message instead of doing the actually earning.

# ? Apr 5, 2012 21:45

h_double: Jul 27, 2001

I don't know about BF Heroes, but BF Bad Company 2 is set up so that you don't earn any xp unless there are (I think) at least six people on the server, to keep you and your buddy from easily grinding unlocks.

# ? Apr 5, 2012 21:49

dizzywhip: Dec 23, 2005

Rupert Buttermilk posted:

Quick question: Does Flixel/Stencyl do parallaxing for 2D platformers?

Look for the scrollFactor property on FlxObject. Just set that to progressively smaller numbers (between 0 and 1) for each layer behind the foreground.

# ? Apr 5, 2012 21:55

xgalaxy: Jan 27, 2004; i write code

Hughlander posted:

Are there any papers or GDC talks on security in a Freemium game? I'm starting to think about ways of authenticating/validating unlocks/purchases but would like to read/watch anything that's already public...

Its highly platform specific question too =)
For iOS as an example, a common mistake is to store unlocks/puchases/etc in UserDefaults. This is bad, because its essentially a plain text file. Store that stuff in the keychain!

# ? Apr 6, 2012 00:15

Jo: Jan 24, 2005; Soiled Meat

If you dominate CPU usage with a tight loop in a Java application, there's a decent chance you'll miss keypress/keyrelease/mouse events.

# ? Apr 6, 2012 00:20

OneEightHundred: Feb 28, 2008; Soon, we will be unstoppable!

h_double posted:

I don't know about BF Heroes, but BF Bad Company 2 is set up so that you don't earn any xp unless there are (I think) at least six people on the server, to keep you and your buddy from easily grinding unlocks.

You can force servers to maintain audit logs and the like, but ultimately it comes down to heuristic checks. That is, you won't be able to distinctly tell if something came from a hacked server or not, so the best you can do is try to detect data that isn't realistically achievable. When possible, they force the main server to be involved in the process, i.e. Valve's games will boot you eventually if you don't have a valid Steam session token, and Steam will invalidate your token and give you a new one if you connect to another server.

Also, long delays between ban waves make it much harder for hackers to tell how they're being detected, not just because of the smaller sample size, but also because it increases the number of things that could have caused a detection on a given account and makes it much harder to single one factor out.

OneEightHundred fucked around with this message at 00:46 on Apr 6, 2012

# ? Apr 6, 2012 00:33

Pfhreak: Jan 30, 2004; Frog Blast The Vent Core!

Rupert Buttermilk posted:

Quick question: Does Flixel/Stencyl do parallaxing for 2D platformers?

I'm pretty sure it does. Here's an example game that uses it: http://jayisgames.com/games/psychopomps/

It's kind of a small indie title though, so you've probably never heard of it. :haw:

# ? Apr 6, 2012 02:56

Rupert Buttermilk: Apr 15, 2007; 🚣RowboatMan: ❄️Freezing time🕰️ is an old P.I. 🥧trick...

Pfhreak posted:

I'm pretty sure it does. Here's an example game that uses it: http://jayisgames.com/games/psychopomps/

It's kind of a small indie title though, so you've probably never heard of it.

poo poo, man, I was JUST ABOUT to post 'Dude... what...?"

Then I kept reading, and reading is power! :eng101:

Anyway, dude, you wanna work together this year again?

# ? Apr 6, 2012 15:04

Harvey Mantaco: Mar 6, 2007; Someone please help me find my keys =(

So is this a thread for sparsly posting what we're currently working on as well?

I don't have much to show right now but I wouldn't mind having a place to show as I go along so people can maybe tell me what is poo poo/good or comment on. If this isn't the place for that then sorry, I'll stop!

Never wrote a game before much more than the odd little app on Android so making my first steps into a roguelike in Java (Black spots under the walls and the wall pieces aren't all sized properly - I'm aware of these but I'm more concerned with moving ahead with the framework of the application before getting into the art... which is tough because it's what I'm most excited about.)

The dungeon randomizer is working and working fast, I diagrammed how I'm going to deal with entities and game structure so I'm just getting that all in place right now. The randomizer can also create caves and rooms with bedrooms and different cool things but it's not perfect yet so I don't have it turned on.

Next in line:
-Add entities, including a controllable character piece.
-Implement less robotic and more realistic non-player entity path-finding as well as direct path-finding for the player.
-Only display/render visible tiles from player entity perspective tiles.
-Begin dungeon Stairs/Non-player entity and "loot" generator/placer.

Mewse posted:

Hahaha the gently caress are you doing in this thread? Why aren't we working on something together? I thought you didn't code anymore.

"I like, I can't even... gently caress. Programming, I can't even like... these loving compilers, they don't even loving work. I am never going to do that poo poo."
-Mewse, 2012

# ? Apr 6, 2012 19:41

HaB: Jan 5, 2001; What are the odds?

Hmm...

K, I am sorta stumped on how to begin something here. Mostly the storage of the data.

If I have a world map that's divided into territories - picture a state map divided into counties, say - and I want to highlight a particular county when the mouse is hovering over it, how would I store the "shape" of the county?

I'm using XNA - does it have some sort of open-ended-number-of-sides polygon? I haven't noticed one anywhere. I figure I could store like a List<Vector2> or something, but for map-style shapes that seems like it could get pretty complex.

What I'm shooting for is a map editor where you can load in a flat terrain image, and then "draw" the territory shapes on it, which it will then save out to some machine-readable map format, or even just XML describing each territory.

So...thoughts?

# ? Apr 6, 2012 20:00

OtspIII: Sep 22, 2002

Harvey Mantaco posted:

The dungeon randomizer is working and working fast, I diagrammed how I'm going to deal with entities and game structure so I'm just getting that all in place right now. The randomizer can also create caves and rooms with bedrooms and different cool things but it's not perfect yet so I don't have it turned on.

Ah, what the hell. I'll use this as an excuse to post my (apparently incredibly similar) project I've been working on, as well.

This is the isometric roguelike-ish thing I've been working on since January. Ignore the graphics--I'm just either doing 2-minute scrawls or stealing sprites off the internet as placeholders until I'm confident that I'm not going to be changing my tile size or anything like that--, but this is more or less how I'm planning for it to work. I say that it's roguelike-ish because it's actually going to be a team game (where you control one guy during exploration and place the rest of the team whenever you enter combat), and the emphasis will be more on smaller lairs that you visit multiple times than big dungeons that you just head down in and never turn back till you hit the bottom. Also ignore the arbitrary distribution of kitchens, since that's what I'm working on currently.

Harvey Mantaco, how are you doing map-generation (if you're willing to spill design secrets)? You look really good (I am super jealous of your walls), but even for a way-dungeony map the complete lack of halls/non-rectangular rooms is throwing me a little. By 'rooms with bedrooms' did you mean more fancily shaped rooms on a layout level or just the types of items that will decorate the room?

# ? Apr 6, 2012 20:20

Harvey Mantaco: Mar 6, 2007; Someone please help me find my keys =(

OtspIII posted:

Harvey Mantaco, how are you doing map-generation (if you're willing to spill design secrets)? You look really good (I am super jealous of your walls), but even for a way-dungeony map the complete lack of halls/non-rectangular rooms is throwing me a little. By 'rooms with bedrooms' did you mean more fancily shaped rooms on a layout level or just the types of items that will decorate the room?

You're jealous? I'm jealous

I'll let you know my general algorithm.

I wanted long hallways with no interruptions to be really sparse.

1. Create a random room with a basic shape, either randomized rectangle, cave, circle, shaped like a skull... whatever. I got a few.
2. Chance of now adding an inner section to the room. So a room inside of the room for example, or a sleeping quarters against a wall with beds in it and such... lots of different things.
3. Once the room is created place it on the "main" map. The first room will go in a random place, every room after that basically has the world generator play a game of Tetris to stick it in a close fitting and available location for a moment. Changing the buffer of how close rooms will be to each other will create a greater chance of longer hallways in the next step.
4. When the room is placed I run an algorithm to find random and reasonable locations for doors on a random side of the room. Once a door is placed a corridor shoots off from the room until it finds another room and if it does it connects and draws the hallway. If no connections are found after X tries then keep track of the failure to place and create another room to try again. If >3 connections are made OR we reach our counter and at least one has been made then finalize the room and place it and go onto the next one. Enough failures and we don't need to draw any more doors, the "main" map is full.

Obviously there is more but that's pretty much it. It's fast and I like how I can basically add any kind of new room or whatever to it and nothing breaks.

Once everything is placed I quickly run through the Array[][] of rooms and it looks at each wall. That wall looks at it's surrounding walls to decide what kind of wall it should be (a wall to the left and right? I'll be a horizontal wall! A wall above and the right? I'll be an L shaped pointing up and right!)

I'm in the same boat with you, I'm not worried about graphics right now until basically the very end of this (never ending goddamn) project.

When I saw your little goblin dudes I smiled, then I saw the one with the crown and I literally laughed out loud. I don't know, caught me off guard.

Harvey Mantaco fucked around with this message at 23:17 on Apr 6, 2012

# ? Apr 6, 2012 20:47

MrPablo: Mar 21, 2003

HaB posted:

Hmm...

K, I am sorta stumped on how to begin something here. Mostly the storage of the data.

If I have a world map that's divided into territories - picture a state map divided into counties, say - and I want to highlight a particular county when the mouse is hovering over it, how would I store the "shape" of the county?

I'm using XNA - does it have some sort of open-ended-number-of-sides polygon? I haven't noticed one anywhere. I figure I could store like a List<Vector2> or something, but for map-style shapes that seems like it could get pretty complex.

What I'm shooting for is a map editor where you can load in a flat terrain image, and then "draw" the territory shapes on it, which it will then save out to some machine-readable map format, or even just XML describing each territory.

So...thoughts?

I'm not familiar with XNA, so I don't know if it has a built-in solution to this type of problem. I can tell you how you deal with this sort of problem in the general case.

You want a list of countries, where each country contains:

country identifier (name, country code, whatever)
geometry of the bounding polygon (a list of vertices)
optionally a bounding box for the bounding polygon (you can generate this at runtime or store it with the geometry itself)

In JSON it might look something like this:

code:

{
  countries: [{
    id:     "us",
    points: [[1, 2], [2, 3], [3, 4]],
    bounds: {"x": 1, "y": 2, "w": 2, "h": 2}
  }, {
    id:     "canada",
    points: [[5, 6], [6, 7], [7, 8]],
    bounds: {"x": 5, "y": 6, "w": 2, "h": 2}
  }]
}

To test for intersections, you can use one of the methods described here: Point in Polgyon.

When the user moves the mouse, you test to see if the mouse coordinates are within the bounding box of the country's polygon. If they are, then you perform the more expensive Point in Polygon calculation above to see if the mouse coordinates are actually within the country's polygon.

If you have a large number of countries, you can also build a spacial index (e.g., a Quadtree) to cut down on the number of bounding box comparisons. You don't even need something as elaborate as a Quadtree; a simple 10x10 grid will probably be sufficient for a list of non-overlapping countries.

So, when the mouse position changes:

Get the spacial index (quadtree or grid) region that the mouse coordinates intersect.
Get a list of countries that intersect the given spacial index region.
Test the mouse coordinates against the bounding box of each country's polygon.
If the mouse coordinates intersect the country's bounding box, then perform a Point in Polygon test of the mouse coordinates against the country's polygon.
If the mouse coordinates intersect with the country, and it is not already highlighted, then mark it as highlighted and redraw the map. If the country is already marked as highlighted, then do nothing.

That should be enough to get you started. I used the technique above to solve a similar problem for a work-related GIS tool.

Edit: fixed JSON quotes.

# ? Apr 6, 2012 21:06

ynohtna: Feb 16, 2007; backwoods compatible; Illegal Hen

An alternate option would be to assume that every clickable pixel only belongs to a single country. (A fair assumption as otherwise what's the response logic when they click on e.g. the exact meeting points of Luxembourg, France and Germany.)

Define your country boundaries with bounding polygons as already specified but then use that to build up an invisible "bitmap" where each "pixel" contains, not a colour, but an index/identifier of the associated country.

Thus determining the country you're hovering above is very fast: just a memory lookup. Highlighting the territory underneath the cursor can then be done with the original polygonal bounds, or if you're feeling old school a simple flood fill. (Naturally, this is only necessary when the underlying country has changed.)

Of course, this solution is inappropriate if your map is continuously scalable or extremely large relative to the target device's memory capacity.

# ? Apr 6, 2012 21:33

OtspIII: Sep 22, 2002

Harvey Mantaco posted:

I'll let you know my general algorithm.

I wanted long hallways with no interruptions to be really sparse.

1. Create a random room with a basic shape, either randomized rectangle, cave, circle, shaped like a skull... whatever. I got a few.

Oh, nice. I came close to doing it somewhat similarly, but I realized I actually did want a lot of hallways and control over the sort of over-flow of the dungeon. Also, the way I tried to do it was pretty inelegant and looked really bad.

My process got a little windy, but it still generates a big map in less than a second so I'm not worrying about it yet (although I'm sure it'll slow the gently caress down once I start populating rooms with a bit more detail).

1. I divide my level into 4 and assign each a pre-drawn pathway grid. Each of those 4 sections is made up of a 3x3 grid of sections of its own, each of which track if they connect to each of their neighbors or not. This results in an overall 6x6 pathway-grid that goes through the whole level but feels fairly randomized (examples below). I do this so that I can artificially make sure there are some choke points and some remote areas in the map, while leaving the map's center fairly maze-like and interconnected. If there are other levels on the same depth or levels below it stairs or more hallways will get spawned, too.

2. I have a list of geomorphs that I then place in each of the open slots in the 6x6 grid. It makes sure that the chosen geomorph has an exit in every direction that the underlying pathway map desires, and rejects any that don't. I actually ended up making the geomorphs themselves pretty flexible, too, so that most of them actually have optional hallways baked into them--if they are supposed to link to the geomorph to their east they grow a hall to the east, and if not that part of the geomorph is just blank.
There's also a bit of randomness baked into them, so that many of the rooms only appear 1/3 of the time or so on, so that people can't just memorize the geomorph shapes and know what's coming up on them. It came out way better than I could have dreamed for--the example I posted above only actually uses 6 geomorphs to populate itself, despite having 34 open slots.

3. I run an audit on the map and let each room know who its neighbors are, how far it is from the dungeon entrance, etc. The idea is that the further you get from the entrance/the shortest path you can take towards the downward staircase, the less traffic there is in the dungeon and the odds of running into monsters goes down, while the odds of running into traps and unlooted treasure goes up.

4. Using the data from the audit I figure out what every room I've placed should be, based on its size, remoteness, the ratio between its height and width, etc. I start by placing monster lairs, then once I've put one team of monsters in the dungeon for every 4 rooms I assign a theme to any room that hasn't already had a theme assigned to it. The 'themes' are the stuff I posted above like 'kitchen' or 'profane temple' or 'goblin throne room'. These spawn things the room's decorations and will probably determine the type of treasure that appears if the room is tagged to contain a treasure hoard (I haven't gotten that far yet).

I'm leaving out a few steps (each dungeon is actually built off of a core set of rumors about it that determines what type of monsters live in it, what its big treasure-hoards look like, etc), but that's more or less it.

Your room placement method sounds really good, based on all the things I'm trying to make sure I worry about. The rooms seem to have a good balance of both branchyness and loopyness, and even though the screenshot you posted is pure rectangles, they do have a really nice variety of sizes and shapes. I'm obsessively hunting for other similar projects I can steal ideas from, so I'm looking forward to seeing you post more updates here in this thread.

# ? Apr 6, 2012 21:49

Null Pointer: May 20, 2004; Oh no!

HaB posted:

Hmm...

K, I am sorta stumped on how to begin something here. Mostly the storage of the data.

...

So...thoughts?

As MrPablo stated, you are trying to solve the point location problem. A good answer to this question will depend on the size and complexity of your map (and the amount of work you're willing to do.)

A typical data structure for planar subdivisions (e.g. maps) is a doubly connected edge list. DCEL is similar to what MrPablo was describing, except it adds some extra information which is useful for building search structures.

ynohtna's solution isn't bad, if you don't need a lot of accuracy. MrPablo's would be okay, if your country boundaries aren't very detailed. If your map is very detailed, you should read up on trapezoidal maps. If you don't want to do any preprocessing at all, beyond the bare minimum for rendering the map, you can usually get good results with a random walk on the Delaunay triangulation.

# ? Apr 6, 2012 22:59

Adbot: ADBOT LOVES YOU

# ? May 25, 2024 19:07

Unormal: Nov 16, 2004; Mod sass? This evening?! But the cakes aren't ready! THE CAKES!; Fun Shoe

Null Pointer posted:

As MrPablo stated, you are trying to solve the point location problem. A good answer to this question will depend on the size and complexity of your map (and the amount of work you're willing to do.)

A typical data structure for planar subdivisions (e.g. maps) is a doubly connected edge list. DCEL is similar to what MrPablo was describing, except it adds some extra information which is useful for building search structures.

ynohtna's solution isn't bad, if you don't need a lot of accuracy. MrPablo's would be okay, if your country boundaries aren't very detailed. If your map is very detailed, you should read up on trapezoidal maps. If you don't want to do any preprocessing at all, beyond the bare minimum for rendering the map, you can usually get good results with a random walk on the Delaunay triangulation.

You could do a BSP (like a doom level) to divide the map into convex hulls then you could check each hull's sides to pick the hull where you're on the 'inside' of every edge. Never solved this problem before, just what popped to mind.

A 'bitmap' with country codes instead of colors is certainly the easiest if you're not memory-constrained though.

# ? Apr 6, 2012 23:05

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Game Development Megathread

«‹›623 »