Game Development Megathread

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

«‹›623 »

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

DancingMachine posted:

Hubis and OneEightHundred give good advice. But at a higher level, if this is your first time dabbling in threads, I would try writing something from the ground up that is parallelized.

Even from a high-level standpoint, I think minimizing contention by design is probably the easiest way to get in to it. The first iteration of my current project was done trying to make subsystem threads and event queues and it the rewrite did nothing of the sort: Having a main thread drive of program flow and having zero concurrency except for jobs actually works pretty well and it's a hell of a lot easier to architect. Conflicts can be avoided by just not allowing jobs to even start if a job they're dependent on isn't finished yet.

Also, focus mainly on making things threadable that actually sap performance. i.e.:
- Vertex transformation sucks up a ton of processing power and is really easy to decompose into jobs. Although you should really find a way to offload that to the GPU.
- Ditto for animation setup.
- Physics can be run while you do render work. i.e. update renderables list from world state, then run physics for the next frame while you draw renderables since you're done using the world state.
- If you want to get super-advanced, Id had a novel approach for threading game objects: Objects can generally only access the state of other objects from the PREVIOUS frame.

# ? Dec 12, 2011 09:14

Adbot: ADBOT LOVES YOU

# ? May 26, 2024 21:48

Rocko Bonaparte: Mar 12, 2002; Every day is Friday!

DancingMachine posted:

Is this your first time doing asynchronous programming?

I was thinking about this a little bit more and I don't think I really got what you were implying. This, as something distinct from concurrency and multithreading, is the first time I've done this from the systems end. Certainly I've used asynchronous systems before when working with stuff like GUIs, but I would have to admit this would be the first time I've stood on the other side of the fence and seen what it looks like.

From that perspective, do you have any good recommendations for reading up on it that treat it distinct from the standard gamut of concurrency stuff?

# ? Dec 12, 2011 23:36

DancingMachine: Aug 12, 2004; He's a dancing machine!

Rocko Bonaparte posted:

I was thinking about this a little bit more and I don't think I really got what you were implying. This, as something distinct from concurrency and multithreading, is the first time I've done this from the systems end. Certainly I've used asynchronous systems before when working with stuff like GUIs, but I would have to admit this would be the first time I've stood on the other side of the fence and seen what it looks like.

From that perspective, do you have any good recommendations for reading up on it that treat it distinct from the standard gamut of concurrency stuff?

That's all I meant - programming with concurrency and multithreading. Have you had to use locks, semaphores, mutexes, critical sections, etc. in your code before. Sounds like I was incorrect in assuming you had no experience there.

# ? Dec 13, 2011 06:58

Rocko Bonaparte: Mar 12, 2002; Every day is Friday!

Well I started to dig into the synchronization stuff by just slapping a lock around the part of the main loop that tells Irrlicht and Bullet to do stuff. Actually, I went completely chronic and put the lock around the whole inside of the loop body. I did this to see how it would respond to a different problem I am seeing--this is just because the mere act of throwing the locks around what I think was the part giving me the grief made the access violation go away. Gotta love it.

Anyways, I am trying to create an entity through Python using wrappers to the C++ code. A new entity gets fetched, and then it starts tagging on components, of which one is representing an animated mesh. This component wants to tell Irrlicht to load a new mesh. Since I was seeing an access violation here, I had it working against the same look as the main loop. Oddly enough, I still get an access violation all the way down in the ATI driver. It looks like Irrlicht's own code was able to load everything up okay to a point. I think the pants making GBS threads happens when Irrlicht starts to transmit the texture down to the card.

I'm wondering if there's some bizarre thread/resource ownership that happens with 3d stuff like you get with GUIs on Windows. I've at least seen this in C# before with Windows Forms stuff that you have to interact with GUI components on the thread they were created, so all this hilarity ensues. I'm kind of wondering if there's something inherent in having code triggered by the Python interpreter thread that would cause this to completely fail.

I'm thinking not, but it's quicker to ask this then to start really messing around with stuff to try to uncover why this could be happening. I'm actually thinking this isn't a race condition or something, so I'd have to write something up that still loads the mesh through Python w/o all the other baggage.

Edit: The initial impression I get is that it's just completely unsafe for the thread that is invoking the Python commands to muck with Irrlicht. I have been doing an experiment where I have the code being wrapped in Python trigger a temporary block in the engine thread to construct the stuff I want. This seems to generate the objects without crashing. So I guess I need to change my code so I don't pass around the Irrlicht and Bullet stuff directly, but rather have the thread that creates them take requests to manipulate them. You know, like you would do properly with abstracting subsystems or something.

Rocko Bonaparte fucked around with this message at 17:57 on Dec 13, 2011

# ? Dec 13, 2011 08:26

ehnus: Apr 16, 2003; Now you're thinking with portals!

OneEightHundred posted:

Even from a high-level standpoint, I think minimizing contention by design is probably the easiest way to get in to it. The first iteration of my current project was done trying to make subsystem threads and event queues and it the rewrite did nothing of the sort: Having a main thread drive of program flow and having zero concurrency except for jobs actually works pretty well and it's a hell of a lot easier to architect. Conflicts can be avoided by just not allowing jobs to even start if a job they're dependent on isn't finished yet.

Also, focus mainly on making things threadable that actually sap performance. i.e.:
- Vertex transformation sucks up a ton of processing power and is really easy to decompose into jobs. Although you should really find a way to offload that to the GPU.
- Ditto for animation setup.
- Physics can be run while you do render work. i.e. update renderables list from world state, then run physics for the next frame while you draw renderables since you're done using the world state.
- If you want to get super-advanced, Id had a novel approach for threading game objects: Objects can generally only access the state of other objects from the PREVIOUS frame.

Completely agree.

Job/task based programming (enabled by something like Intel's TBB)is really the way to go when it comes to making games run across multiple processors. The hardest part of concurrency is dealing with contention of shared resources and job-based architectures make it much easier to simply avoid having multiple threads work on the same data at the same time. Data flows tend to be much more clearly laid out in job-based games which makes the engine much easier to understand and work with.

Job based games also makes it much easier to leverage heterogenous architectures (SPUs, GPGPU) into your program if you have such a desire down the road. You can kick work off to the GPU and continue processing jobs on your main processor in parallel, preventing blocking until the GPU has finished its work.

# ? Dec 13, 2011 17:26

Rocko Bonaparte: Mar 12, 2002; Every day is Friday!

I can see that generally as a good architectural methodology. There is a lot of stuff out there. The one place where I don't really see anything is how to incorporate scripting into a multithreaded engine. Actually, I don't see much about the technical implications of incorporating scripting generally.

Imagine I have some thousand lines of scripting code for some basic but complete game, and there's an engine doing its own thing. There's plenty of code there that, if left to its own devices, would probably affect objects that the engine is actively using, causing all hell to break loose. I see two main ways around it. One is to spin on the contested resources, and the other is to just enqueue the scripting command to get processed whenever; I guess that would be like running jobs.

With the spin, I imagine a case where if my frame rate was basically 60 FPS that due to the contention, I could only get 60 commands through. Is this paranoia?

With the enqueuing, I imagine temporality becomes a huge bitch. At some point in the script I have to be sure what was put in previously is actually active.

# ? Dec 13, 2011 17:55

DrMelon: Oct 9, 2010; You can find me in the produce aisle of the hospital.

Working on a little roguelike that plays with the idea of role-reversal.

Currently in very early stages and cribbing heavily from tutorial sources, though I have been cleaning up and refactoring the code along the way (one particularly useful tutorial is done all in one file, globals everywhere :psyboom:

)

# ? Dec 13, 2011 19:24

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

Rocko Bonaparte posted:

I can see that generally as a good architectural methodology. There is a lot of stuff out there. The one place where I don't really see anything is how to incorporate scripting into a multithreaded engine. Actually, I don't see much about the technical implications of incorporating scripting generally.

Keep in mind that a lot of scripting APIs like Lua have global locks and only allow one thread to use them in the first place. Game object scripting is really not very intensive, though pathfinding and collision checks can be.

If you really want to thread game logic, then generally what happens is objects cause interactions to accumulate on other objects which are executed on the NEXT behavior update, and physics/animation updates do not happen until the behavior code is finished.

i.e.:
Frame 1: Player 1 shoots a railgun, it traces to hit the physics box of player 2. Adds a "take damage from railgun" event to Player 2's event queue. Player 2 does nothing because the event won't take effect until the next frame.
Frame 2: Player 2 processes processes "get railed" event, determines that it's time to explode into chunks. Adds some "spawn gib" events to the next frame's queue and flags itself for removal. Physics updates do not take effect yet, so if another player fires a shot at player 2's location, they will still hit the collision hull.
Post frame 2: Player object is removed, chunks are spawned, physics are run.

quote:

There's plenty of code there that, if left to its own devices, would probably affect objects that the engine is actively using, causing all hell to break loose. I see two main ways around it. One is to spin on the contested resources, and the other is to just enqueue the scripting command to get processed whenever; I guess that would be like running jobs.

Like I said, design things in a way that they're decomposable and don't content resources. See the gamecode example: You can have all of your threads utilized processing game objects except for the very brief period that you need to wait for them to complete, and after that you can run physics and rendering setup. Physics aren't a contended resource in that case because the main thread will not even start physics jobs until the behavior code modifying the physics state finishes.

I guess I should put it this way: The entire point of threading is to exploit lack of resource contention, so you should be focusing on ways to thread non-contending algorithms and make algorithms that contend less.

OneEightHundred fucked around with this message at 21:42 on Dec 13, 2011

# ? Dec 13, 2011 19:56

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

DrMelon posted:

Working on a little roguelike that plays with the idea of role-reversal.

Currently in very early stages and cribbing heavily from tutorial sources, though I have been cleaning up and refactoring the code along the way (one particularly useful tutorial is done all in one file, globals everywhere )

Fun idea. I've always wanted to make the procedural content part of a rogue-like, but I have so little interest in the gameplay aspects. Things like writing setting, combat, UI, don't do anything for me. Looks like you have a fun thing going!

# ? Dec 13, 2011 20:37

beauty queen breakdown: Dec 21, 2010; partially cromulent posting.
"2021's worst kept secret"

configuration
I am using Javascript with HTML5 in Chrome. Not sure if this is the best place to ask this but would be happy to move the question if there's a more relevant thread. (the javascript question/answer thread did not seem the appropriate place to ask)

background
I am writing what amounts to a 2D breakout clone. Here is the relevant portion of the collision function:

code:

if(bally < 5*55+30 && bally > 30 && ballx < 10*65+70 && ballx > 70)
	{
		var dbx = Math.floor((ballx-70)/65);
		var dby = Math.floor((bally-30)/55);
		
		if ( blocks[dbx][dby] != 0)
		{
			if((ballx + 10) > (dbx*65+70) && ballx < (dbx*65+120))
				balldy = -balldy;
			else
				balldx = -balldx;
			blocks[dbx][dby] = 0;
		}
	}

I've removed my comments, so for clarity:
The first if is checking to see if the ball is within the rectangular box containing blocks;

the first nested if checks to see if the block contained in the array has been destroyed already;

the final if/else checks to see which side of the block the ball struck (so it bounces off in the logical direction).

Problem

Collisions are checked each time the screen is drawn (currently hard-capped at roughly 33 fps). When the change in x and y of the ball are 5, collisions work pretty well (still some cleanup to do) as the blocks and their positions are generally divisible by 5 in both directions. If the change in x or y changes at all, collisions get very odd because the ball leaps several pixels into the block before the code notices it has 'collided.'

Question

Is there a best-practice here? I have thought of 'looking ahead' -- i.e. iterating through where the ball will be between frames and checking collisions that way -- but I can't suss out the math (keeping in mind that the change in x does not always necessarily equal the change in y). Am I solving the wrong problem -- i.e. should I be calculating collisions differently, or moving the ball faster than the framerate, or something else I haven't thought of?

Any and all help is greatly appreciated. In the meanwhile, I'll edit shortly with some screencaps of the work in progress.

e: screencaps:

beauty queen breakdown fucked around with this message at 23:23 on Dec 13, 2011

# ? Dec 13, 2011 23:16

PDP-1: Oct 12, 2004; It's a beautiful day in the neighborhood.

Rocko Bonaparte posted:

Multi-threaded game engine stuff

I played around with making a multi-threaded game engine a few months ago, and one important consideration for this kind of game engine is timing. If you have one main Update/Draw thread and 27 background task threads running at the same time your framerate will swing around wildly. To make things stable I had to do two things:

(1) Create a pool of low-priority worker threads where the number of threads was roughly equivalent to the number of available CPU cores, plus queues for unprocessed and processed tasks. Each worker thread would try to grab the next available unprocessed task, run it's generic Execute() method, and place the finished task in the processed item queue. Then the main Update/Draw thread could synchronously grab all items out of the processed queue and apply their results.

(2) Your main Update/Draw loop has to be 'sleepy' in the sense that you want it to execute one time and then cede back any remaining CPU time to be used by the worker threads until the next clock tick. In other words, you don't want to enter a tight loop where you're just looking at the system clock over and over waiting for the next multiple of 1/60th of a second since that would just be wasting CPU cycles that the worker threads could use. Instead I ran Update/Draw once and then blocked the thread until a system timer signaled that it was OK to proceed.

By doing those two things I was able to get ~95% CPU usage on my dual-core machine and keep the framerate mostly locked at 60FPS. I say mostly here, because when you get that close to 100% CPU usage any additional system activity will cause a few frames to skip.

DrMelon posted:

Working on a little roguelike that plays with the idea of role-reversal.

That looks cool, nice job!

I also like the role-reversal theme and sometimes kick around ideas for reversing classic/popular games. Someday I'm gonna write a game called Placid Pigs, about a family of pigs that just wants to sit around their house minding their own business but these rear end in a top hat birds keep trying to knock the place down. Kind of a realtime builder/defense game.

# ? Dec 13, 2011 23:47

mewse: May 2, 2006

Lord Byron III posted:

Question

Is there a best-practice here? I have thought of 'looking ahead' -- i.e. iterating through where the ball will be between frames and checking collisions that way -- but I can't suss out the math (keeping in mind that the change in x does not always necessarily equal the change in y). Am I solving the wrong problem -- i.e. should I be calculating collisions differently, or moving the ball faster than the framerate, or something else I haven't thought of?

You should be looking ahead.

You can view the ball as a bounding circle and do collision detection on the center of the ball vs the edges of the blocks, offset by the ball's radius.

That means you create a ray that is a line segment, ball center x/y starting position, ball center x/y post-velocity.

Then loop through each (active) block on the field:

If ball's x velocity is positive:
Does the ray pass through (block's left side - ball radius)?

etc for the other three directions

After that, to make it really bullet proof, you resolve the collisions by finding which block the ball hits first, and creating another line segment with the remaining velocity post-collision, and doing another round of collision detection on that. That will solve the problem if the ball hits multiple blocks in a single frame.

Easier said than done and this might not even be the best way to do it.

# ? Dec 14, 2011 00:25

Dr. Dos: Aug 5, 2005; YAAAAAAAY!

DrMelon posted:

Working on a little roguelike that plays with the idea of role-reversal.

Currently in very early stages and cribbing heavily from tutorial sources, though I have been cleaning up and refactoring the code along the way (one particularly useful tutorial is done all in one file, globals everywhere )

This is a neat idea. I had the idea for a backwards roguelike myself where you'd start at the bottom of the dungeon getting the magic artifact but it was cursed and drained your spirit so that with every floor you rose you became weaker and weaker and lost abilities making it so you began the game easily killing ancient dragons or something and then fleeing from kobolds at the end.

# ? Dec 14, 2011 02:03

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Dr. Dos: I'm starting work on something similar for a backwards Zelda, where you start with a bunch of pieces of equipment and you have to give them up one at a time to make your way out of the dungeon, resetting traps and filling chests as you go.

# ? Dec 14, 2011 03:59

Nalin: Sep 29, 2007; Hair Elf

Rocko Bonaparte posted:

So I guess I need to change my code so I don't pass around the Irrlicht and Bullet stuff directly, but rather have the thread that creates them take requests to manipulate them. You know, like you would do properly with abstracting subsystems or something.

Yes. Irrlicht is not thread safe. At all. Do not touch anything related to Irrlicht while in another thread; you are just asking for trouble. If you want to multi-thread stuff, develop a type of job system. The Irrlicht thread can then ask if the job is done, and, if it is, grab and parse the data. You will want to keep everything away from the Irrlicht thread and anything that it touches. Do as much of the work as you can and let Irrlicht do the rest.

# ? Dec 14, 2011 04:18

Rocko Bonaparte: Mar 12, 2002; Every day is Friday!

Nalin posted:

Yes. Irrlicht is not thread safe. At all. Do not touch anything related to Irrlicht while in another thread; you are just asking for trouble. If you want to multi-thread stuff, develop a type of job system. The Irrlicht thread can then ask if the job is done, and, if it is, grab and parse the data. You will want to keep everything away from the Irrlicht thread and anything that it touches. Do as much of the work as you can and let Irrlicht do the rest.

This is good to know because I've been spending a lot of time now throwing Irrlicht in its own little pen and making everything outside interact with it through a slit in the door. However, I'm just for starters trying to avoid an contention by having Irrlicht's render call sitting inside a lock that all the helpers also get before trying to stir the pot. I don't think this helped me earlier, so I'll have to do something with jobs too.

Coming to a C++ programming thread near you: A question about how I could do that with Boost and template voodoo without having to write a bunch of stupid classes.

# ? Dec 14, 2011 08:08

StealthArcher: Jan 10, 2010

Rocko Bonaparte posted:

This is good to know because I've been spending a lot of time now throwing Irrlicht in its own little pen and making everything outside interact with it through a slit in the door. However, I'm just for starters trying to avoid an contention by having Irrlicht's render call sitting inside a lock that all the helpers also get before trying to stir the pot. I don't think this helped me earlier, so I'll have to do something with jobs too.

Coming to a C++ programming thread near you: A question about how I could do that with Boost and template voodoo without having to write a bunch of stupid classes.

Simple question for you all, take a game like Dwarf Fortress, Minecraft, Infiniminer or Terraria (or any like them in some regard). How exactly would be the best way to store all the pieces of the world in memory, assuming a number of them over 2 million (low for Minecraft and Terraria)?

A standard array would be a huge sink, especially assuming several variables making up the class behind the pieces, even assuming just an array of pointers, you're looking at 8 million bytes in a straight run on memory space.

A linked list would consume even more as now you're adding two more 4 byte pointers to each element of the list, now looking at 24 MB.

I don't quite know how much a vector would use.

Even assuming the pointer space itself is low, you still need to link to now 2 million or more individual block classes (assuming the ability to individually interact) looking at possibly a couple gigabytes of total RAM taken unless I'm looking at this all wrong.

# ? Dec 15, 2011 04:23

Orzo: Sep 3, 2004; IT! IT is confusing! Say your goddamn pronouns!

Edit: nevermind, archive.org to the rescue!

Orzo fucked around with this message at 05:36 on Dec 15, 2011

# ? Dec 15, 2011 05:31

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

StealthArcher posted:

Simple question for you all, take a game like Dwarf Fortress, Minecraft, Infiniminer or Terraria (or any like them in some regard). How exactly would be the best way to store all the pieces of the world in memory, assuming a number of them over 2 million (low for Minecraft and Terraria)?

A standard array would be a huge sink, especially assuming several variables making up the class behind the pieces, even assuming just an array of pointers, you're looking at 8 million bytes in a straight run on memory space.

A linked list would consume even more as now you're adding two more 4 byte pointers to each element of the list, now looking at 24 MB.

I don't quite know how much a vector would use.

Even assuming the pointer space itself is low, you still need to link to now 2 million or more individual block classes (assuming the ability to individually interact) looking at possibly a couple gigabytes of total RAM taken unless I'm looking at this all wrong.

If you really need elaborate per-block information, then store fresh blocks as references to an immutable default instance of that block type, and replace it with a newly-spawned instance if something about it needs to change.

# ? Dec 15, 2011 05:45

roomforthetuna: Mar 22, 2005; I don't need to know anything about virii! My CUSTOM PROGRAM keeps me protected! It's not like they'll try to come in through the Internet or something!

OneEightHundred posted:

If you really need elaborate per-block information, then store fresh blocks as references to an immutable default instance of that block type, and replace it with a newly-spawned instance if something about it needs to change.

Also, if your world is mostly comprised of the same few things (eg. empty, mud, water) you could make a first-layer representation of the world as an array of small numbers of bits or bytes, with most of the values representing common blocks and one value in the field representing "look it up in a second layer because it's not one of the common blocks". That way you can still have complex data for blocks that have taken damage or are alive or covered in slime or whatever, but the bulk of your data is dramatically shrunk, at a cost of somewhat slower lookups for the non-simple data - but since most of the data isn't in that category, that's not too big a sacrifice. The bigger sacrifice is probably the added fiddliness of the code.

The second layer would have to be some sort of sparse data structure, obviously, or it'd be pointless.

# ? Dec 15, 2011 06:03

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

StealthArcher posted:

Minecraft stuff...

Most games I've seen write a generic block class with a 'type' variable that's a byte or a short. Most blocks can use this generic type rather than a sub-class. (ie, stone block, rock block, cement block are all just generic block with different values for 'type'.)

You can subclass/aggregate differently when you need to for really special block types like water or whatever. I don't think Minecraft even does that. This is from memory, but I think they just give each block a few bytes of 'data' and depending on the 'type' of the block, handle the data differently. So like wheat blocks might use the data variable to store the maturation, while wood blocks might use it to render a different texture.

Since each chunk in minecraft is 16x16x128, and each block only really stores 'data' and 'type' and maybe a few other flags, the memory footprint isn't that huge per chunk. Then it simply becomes a matter of loading only the chunks near the player into memory.

# ? Dec 15, 2011 08:55

Null Pointer: May 20, 2004; Oh no!

Pfhreak posted:

Most games I've seen write a generic block class with a 'type' variable that's a byte or a short.

Please don't do this, especially not in managed languages. You're sacrificing a lot and the productivity gain will be minimal.

roomforthetuna has a good solution.

# ? Dec 15, 2011 20:21

StealthArcher: Jan 10, 2010

Null Pointer posted:

Please don't do this, especially not in managed languages. You're sacrificing a lot and the productivity gain will be minimal.

roomforthetuna has a good solution.

I'm writing in C++, so not a managed language (if I'm getting your definition right?)

But yes, looking at tuna's idea, a standard array for the first layer and an SVO for the second should work well right?

# ? Dec 15, 2011 21:52

roomforthetuna: Mar 22, 2005; I don't need to know anything about virii! My CUSTOM PROGRAM keeps me protected! It's not like they'll try to come in through the Internet or something!

StealthArcher posted:

I'm writing in C++, so not a managed language (if I'm getting your definition right?)

But yes, looking at tuna's idea, a standard array for the first layer and an SVO for the second should work well right?

I would have gone with a hash/map rather than an octree for the second layer, since you're wanting to reference it by specific coordinates, not look through it by volumes. Though you could just have a list of special blocks per chunk, and cache the combined data from the two sets into an uglier big array for all the nearby blocks, which would be more like the octree way - so the ugly array would be your cache of data that's actively in use, and the less ugly array-plus-list would be the saved 'background' data.

# ? Dec 15, 2011 22:12

StealthArcher: Jan 10, 2010

roomforthetuna posted:

I would have gone with a hash/map rather than an octree for the second layer, since you're wanting to reference it by specific coordinates, not look through it by volumes. Though you could just have a list of special blocks per chunk, and cache the combined data from the two sets into an uglier big array for all the nearby blocks, which would be more like the octree way - so the ugly array would be your cache of data that's actively in use, and the less ugly array-plus-list would be the saved 'background' data.

A hash sounds more efficient now that you bring it up. I'll try an implementation of both out and see what works.

# ? Dec 15, 2011 22:21

Orzo: Sep 3, 2004; IT! IT is confusing! Say your goddamn pronouns!

So, in implementing my own collision detection/response for a 2D platformer, I feel like I'm jumping into a pit of hell where there's thousands of other people, some of them who have been there for years and years, some of them doing some really weird tricks who are sort of escaping from said pit, with maybe an article or two of their clothing on fire as they sort-of solve their problems. Okay, terrible analogy, but you get the picture.

There's so many resources on this that I've spent hours reading, but none of them really seem to provide a definitive solution to the problem of finding the minimum displacement vector from multiple simultaneous collisions. I am using the separating axis theorem and testing arbitrary convex polygons against each other.

Does anyone have any resources that helped them overcome a similar problem? There are cases such as 'player is falling and pushing against a wall made up of adjacent rectangles' and 'pushing into a corner' that seem to generate difficult cases.

# ? Dec 15, 2011 22:45

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

Orzo posted:

There's so many resources on this that I've spent hours reading, but none of them really seem to provide a definitive solution to the problem of finding the minimum displacement vector from multiple simultaneous collisions. I am using the separating axis theorem and testing arbitrary convex polygons against each other.

Does anyone have any resources that helped them overcome a similar problem? There are cases such as 'player is falling and pushing against a wall made up of adjacent rectangles' and 'pushing into a corner' that seem to generate difficult cases.

Why on earth do you need depenetration in a 2D platformer? You're going for simple collisions, not rigid body interactions. (or so I'd assume from your initial question)

2D platformer collision amounts to box vs box, if collision found, slide box toward its previous position by overlap X and overlay Y. You're way overcomplicating things, unless you want rigid body physics (in which case - use Box2D).

# ? Dec 15, 2011 22:51

Orzo: Sep 3, 2004; IT! IT is confusing! Say your goddamn pronouns!

Shalinor posted:

Why on earth do you need depenetration in a 2D platformer? You're going for simple collisions, not rigid body interactions. (or so I'd assume from your initial question)

2D platformer collision amounts to box vs box, if collision found, slide box toward its previous position by overlap X and overlay Y. You're way overcomplicating things, unless you want rigid body physics (in which case - use Box2D).

Your algorithm fails for a number of situations, though, two of which I already wrote at the end of my previous post. For example, if I'm falling down and pushing right against a wall, you might imagine my velocity is (1, -1). A displacement due to overlap might be something like (-0.1, 0.1), which would leave me suspended in mid-air.

Don't dismiss this outright as over-complicating, this is an extremely common topic with respect to platformer development.

# ? Dec 15, 2011 23:04

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

Orzo posted:

Your algorithm fails for a number of situations, though, two of which I already wrote at the end of my previous post. For example, if I'm falling down and pushing right against a wall, you might imagine my velocity is (1, -1). A displacement due to overlap might be something like (-0.1, 0.1), which would leave me suspended in mid-air.

Don't dismiss this outright as over-complicating, this is an extremely common topic with respect to platformer development.

If you're falling down and pressing right against a wall, your maximum possible interpenetration with the wall that frame is miniscule. You do a quick check of your bounding volume vs the wall, which is, I presume, multiple bounding volumes of a size smaller than the player, likely meaning you are interpenetrating with multiples. You abstract them into a single collision volume, because merging their contacts would be insane, and you quickly realize that you are penetrating on only one side. You zero X velocity and depentrate, resolve collisions again (no further collision), and continue falling.

Where this gets nasty is if you have a wall with a gap in it, that can't be generalized into a solid collider / where your toe could conceivably have nudged in. The solution there is, basically, to really not do that / to avoid such conditions. In that specific case, if there had to be a gap there, I would recommend putting an invisible collider there that hit the player but didn't hit whatever could fit through that gap.

EDIT: The second you involve what you're talking about, generating and merging contacts, you've stepped in the direction of rigid bodies. I really wouldn't recommend that for a Mega Man-esque game; It'll add some very, very hard to track fuzziness as a result of numerical inaccuracy when you merge contacts. It's also more math than the NES could have handled, which is the red flag I use when emulating older game systems - "could they have done this on the system in question."

EDIT2: I think you could also handle this case by two-phasing your collision response. First handle penetrations involving only one side, re-evaluate, then handle penetrations involving two sides. So long as your characters were always adjacent to three tiles, the middle tile would resolve first, depentrate, and catch the edge-case before the two angles had a change to knock the character in a funny direction.

Shalinor fucked around with this message at 23:23 on Dec 15, 2011

# ? Dec 15, 2011 23:13

roomforthetuna: Mar 22, 2005; I don't need to know anything about virii! My CUSTOM PROGRAM keeps me protected! It's not like they'll try to come in through the Internet or something!

Orzo posted:

Your algorithm fails for a number of situations, though, two of which I already wrote at the end of my previous post. For example, if I'm falling down and pushing right against a wall, you might imagine my velocity is (1, -1). A displacement due to overlap might be something like (-0.1, 0.1), which would leave me suspended in mid-air.

The way I've done it in the past that's not horrendously complicated, and doesn't fall apart in your scenarios, is first to make the collisions effectively happen with lines rather than blocks (ie. if you hit a box on its top edge, you've collided with the line from its top left to its top right). Then you can do a perpendicular displacement (via dot product with the normal to the line) to prevent penetration of the block, and continue resolving collisions using your newly adjusted movement from the original position.

This way if you're pressing against, or hitting, a wall while falling, you'll lose the horizontal component of your movement but there'll be no change to the vertical. This can be a bit weird if you have diagonal surfaces though - if you fall straight down onto a diagonal slope, you'll pick up some horizontal motion from the depenetration which is dependent on how far you penetrated in that one frame - however, if your velocity is based on how you moved in the previous frame, you'll still be going mostly down if the penetration was small, so the *re*-penetration in the next frame will add the same amount of horizontal motion as you could have in one frame, so it actually works out pretty well. Which is to say, I recommend making it so that collision depenetration acts by changing your velocity for that frame until you're not penetrated.

And if you're pressing into a corner, you'll be rejected in both directions equally, turning your final velocity into an appropriate (0,0).

Edit: if you're working with square surfaces you don't actually need to do a dot product, obviously, you can just change the x or y velocity by the obvious amount. But if you have slopes, the dot product is helpful.

roomforthetuna fucked around with this message at 23:23 on Dec 15, 2011

# ? Dec 15, 2011 23:21

Orzo: Sep 3, 2004; IT! IT is confusing! Say your goddamn pronouns!

Okay, I actually haven't planned in implementing merging polygons into a single body. It seems like that's really inflexible for reasons you mentioned--it can't handle things like small gaps. It's also fairly difficult for dynamic geometry, since you'd have to recalculate the merges every frame. Imagine a platform inside a wall that sticks out a few inches every few seconds, then goes back into a hole--does it become 'merged' with the wall when it's all the way in?

# ? Dec 15, 2011 23:22

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

Oh, wait, I'm overthinking this. The character would see such a collision as a collision with its side, and only its side, regardless. You should be able to recognize a box collision that is entirely "contained" within a side and evaluate it as a side-only collision, and any collision on the top or bottom corner of the character volume that hits both planes should never be deep enough to trigger as a "vertical" collision over a "horizontal" collision in the wall case so long as you're running at a sufficiently high FPS.

EDIT: I was thinking of it in terms of being tile-assertive instead of the collisions being character-assertive, basically. If you think of the interaction as "character depentrating" instead of "tile pushing out", it clears up quite a bit.

EDIT2: Bah, I can't articulate this, there are still edge cases... this is a well-worn algorithm that comes up in every book I've read about 2D tile collision detection. I can go dig an article out if it would help, but I'm almost positive this is typically discussed in any discussion of a tile-based engine. Can't recall how I solved it last time. Either way, you don't want to go the contact merging route typically, you want to detect the case and handle it rote.

Shalinor fucked around with this message at 23:32 on Dec 15, 2011

# ? Dec 15, 2011 23:23

Orzo: Sep 3, 2004; IT! IT is confusing! Say your goddamn pronouns!

Shalinor posted:

EDIT2: I think you could also handle this case by two-phasing your collision response. First handle penetrations involving only one side, re-evaluate, then handle penetrations involving two sides. So long as your characters were always adjacent to three tiles, the middle tile would resolve first, depentrate, and catch the edge-case before the two angles had a change to knock the character in a funny direction.

I must admit that I have no idea what you're talking about here, I think I'd have to see this visually. There are no 'tiles', just arbitrary quads or triangles positioned in space, so there's no guarantee that there's some sort of limit of 2 or collisions.

roomforthetuna posted:

The way I've done it in the past that's not horrendously complicated, and doesn't fall apart in your scenarios, is first to make the collisions effectively happen with lines rather than blocks (ie. if you hit a box on its top edge, you've collided with the line from its top left to its top right). Then you can do a perpendicular displacement (via dot product with the normal to the line) to prevent penetration of the block, and continue resolving collisions using your newly adjusted movement from the original position.

Yes, I think this is similar to what the game 'N' does, for their tiles they define 'solid' edges so that the model is actually sort of a border. Internal edges are then ignored. It's a pretty good solution I suppose, but doesn't quite solve the problem of dynamic objects where an edge might be internal at one time and 'real' in another time, such as the platform that moves in and out of a wall like I described above.

# ? Dec 15, 2011 23:33

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

Orzo posted:

I must admit that I have no idea what you're talking about here, I think I'd have to see this visually. There are no 'tiles', just arbitrary quads or triangles positioned in space, so there's no guarantee that there's some sort of limit of 2 or collisions.

I was thinking in terms of Mega Man-esque tile worlds, where each tile is an independent box that must be intelligently merged with other adjacent boxes in some way. The above suggestion would involve not merging them at all, treating each as an independent collider, then running two collision passes to catch single edge before double edge penetrations with said box cloud. The prior suggestion could involve intelligently merging those tiles as a pre-process step into large colliders not unlike what you're using now.

... but you're talking about separating the collision model from the visual entirely, so that goes out the window. I gather you're drawing collision polygons, or equivalent.

Orzo posted:

Yes, I think this is similar to what the game 'N' does, for their tiles they define 'solid' edges so that the model is actually sort of a border. Internal edges are then ignored. It's a pretty good solution I suppose, but doesn't quite solve the problem of dynamic objects where an edge might be internal at one time and 'real' in another time, such as the platform that moves in and out of a wall like I described above.

Why wouldn't the wall be solid in that case, with the platform sliding out to catch the character, or sliding in far enough / disabling when slid in such that no collision with the wall+platform was ever even possible?

Truly dynamic objects, you'll never likely be able to merge the surfaces well enough. A platform, however, could be pretty well hard-coded to line up precisely and then either modify its collision or run a (relatively) quick merge-collisions pass on nearby tiles. Or, as stated, just bump the platform in far enough that its collisions when retracted are of no concern to anyone.

Shalinor fucked around with this message at 23:49 on Dec 15, 2011

# ? Dec 15, 2011 23:43

Orzo: Sep 3, 2004; IT! IT is confusing! Say your goddamn pronouns!

Shalinor posted:

Why wouldn't the wall be solid in that case, with the platform sliding out to catch the character, or sliding in far enough / disabling when slid in such that no collision with the wall+platform was ever even possible?

Truly dynamic objects, you'll never likely be able to merge the surfaces well enough. A platform, however, could be pretty well hard-coded to line up precisely and then either modify its collision or run a (relatively) quick merge-collisions pass on nearby tiles. Or, as stated, just bump the platform in far enough that its collisions when retracted are of no concern to anyone.

Actually, I was thinking of a hole in the wall. Rather than the platform going in and out of the wall, it's going in and out of a hole in the wall, or a slot. The situation can be modeled with 3 squares stacked up vertically, where the middle one moves to the left to jut out, and then back in again. I feel like hard-coding this particular scenario would get really old after a while, especially since I'm allowing for arbitrary orientations. Moving it in a little more also wouldn't work because it would create a gap (that is, if I'm using a hole, not a solid wall).

# ? Dec 15, 2011 23:56

roomforthetuna: Mar 22, 2005; I don't need to know anything about virii! My CUSTOM PROGRAM keeps me protected! It's not like they'll try to come in through the Internet or something!

Orzo posted:

Yes, I think this is similar to what the game 'N' does, for their tiles they define 'solid' edges so that the model is actually sort of a border. Internal edges are then ignored. It's a pretty good solution I suppose, but doesn't quite solve the problem of dynamic objects where an edge might be internal at one time and 'real' in another time, such as the platform that moves in and out of a wall like I described above.

Since you're not actually running on an 8 bit machine, you could just let everything have edges wherever, run the collision detection as I described, but instead of resolving collisions as they're found, resolving whichever collision is closest to where the character was, first, then going through again whenever there was an adjustment, with the new frame-velocity, looking for new ones. That way you would never actually resolve a collision with an internal edge even if you find one, because the external edge would resolve first and in the second pass the internal one would no longer be hit. I wasn't suggesting you actually create a whole extra map of edges or anything, just that you convert a tile into the appropriate edge when it's collided with as an aid to resolving it appropriately - since you have essentially a line representing where the player moved this frame, that line will always hit one side of the tile first (or, in the event of a perfect corner hit, you can just choose arbitrarily or based on which way you're moving fastest, or you could even consider the normal for that collision to be pointing out of the corner, whatever works best).

The catch with this model is that if you eg. get crushed between a moving platform and a floor you get an infinite loop of resolving the collisions. Fairly easily resolved by having a special case where if you're still resolving solid collisions after ten passes you explode, or whatever resolution you plan to use for situations where a set of collisions actually can't resolve properly no matter what system you use. If you had that situation in Box2D the object would most likely get fired out of the nearest gap at a ridiculous velocity.

# ? Dec 15, 2011 23:57

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

Orzo posted:

Actually, I was thinking of a hole in the wall. Rather than the platform going in and out of the wall, it's going in and out of a hole in the wall, or a slot. The situation can be modeled with 3 squares stacked up vertically, where the middle one moves to the left to jut out, and then back in again. I feel like hard-coding this particular scenario would get really old after a while, especially since I'm allowing for arbitrary orientations. Moving it in a little more also wouldn't work because it would create a gap (that is, if I'm using a hole, not a solid wall).

Well, yes, but why is the hole physically there at all? Does it serve a gameplay function?

You're painting collisions independent from visuals, and the platform needn't care about wall collisions. Why not just paint a solid collision wall, let the platform pull back into said collision wall, demonstrate the hole visually only, and implement platform AI with an "off" / pulled back state and an "on" / not pulled back state to catch the edge-on-edge collider case that would exist in their retracted state?

EDIT: ... the argument I am working around to is that it sounds like you're trying to build a physically perfect system without a clear purpose. Elegant systems for the sake of elegant systems. It would help to have some idea of the game being designed, and the requirements put upon the system.

Shalinor fucked around with this message at 00:05 on Dec 16, 2011

# ? Dec 15, 2011 23:59

Orzo: Sep 3, 2004; IT! IT is confusing! Say your goddamn pronouns!

roomforthetuna posted:

Since you're not actually running on an 8 bit machine, you could just let everything have edges wherever, run the collision detection as I described, but instead of resolving collisions as they're found, resolving whichever collision is closest to where the character was, first, then going through again whenever there was an adjustment, with the new frame-velocity, looking for new ones. That way you would never actually resolve a collision with an internal edge even if you find one, because the external edge would resolve first and in the second pass the internal one would no longer be hit. I wasn't suggesting you actually create a whole extra map of edges or anything, just that you convert a tile into the appropriate edge when it's collided with as an aid to resolving it appropriately - since you have essentially a line representing where the player moved this frame, that line will always hit one side of the tile first (or, in the event of a perfect corner hit, you can just choose arbitrarily or based on which way you're moving fastest, or you could even consider the normal for that collision to be pointing out of the corner, whatever works best).

The catch with this model is that if you eg. get crushed between a moving platform and a floor you get an infinite loop of resolving the collisions. Fairly easily resolved by having a special case where if you're still resolving solid collisions after ten passes you explode, or whatever resolution you plan to use for situations where a set of collisions actually can't resolve properly no matter what system you use. If you had that situation in Box2D the object would most likely get fired out of the nearest gap at a ridiculous velocity.

This is a great idea and I think I'm going to trend towards doing this, thanks. I really do want to avoid manually specifying internal edges in a map editor, resolving vs the edges closest to the original model position seems like a fairly robust solution.

Shalinor posted:

Well, yes, but why is the hole physically there at all? Does it serve a gameplay function?

You're painting collisions independent from visuals, and the platform needn't care about wall collisions. Why not just paint a solid collision wall, let the platform pull back into said collision wall, demonstrate the hole visually only, and implement platform AI with an "off" / pulled back state and an "on" / not pulled back state to catch the edge-on-edge collider case that would exist in their retracted state?

EDIT: ... the argument I am working around to is that it sounds like you're trying to build a physically perfect system without a clear purpose. Elegant systems for the sake of elegant systems. It would help to have some idea of the game being designed, and the requirements put upon the system.

The hole is there in this example because I don't want to design a system with totally arbitrary and bizarre limitations. It was meant to illustrate a reasonably scenario.

I don't need to provide a full game specification and map layouts to you in order to justify wanting solid physics. To say 'it would help to have some idea of the game' is assuming way too much on your part, I have no idea why you'd assume I haven't done anything except poetically muse about physics. Sorry if that sounds defensive, I really do appreciate your insight and resources, but I actually have done quite a bit of real game design for this project.

# ? Dec 16, 2011 00:16

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

Orzo posted:

I really do appreciate your insight and resources, but I actually have done quite a bit of real game design for this project.

Never meant to imply otherwise. You suggested Mega Man-esque physics were a rough target, but weren't happy with the ultimate limitations of Mega Man-esque physics. It was starting to sound like maybe the game was meant to be more physically complicated, so, was curious if there was further detail available as to what problems needed solving.

... but this is now irrelevant, since you're happy with roomforthetuna's solution, so huzzah, problem solved.

# ? Dec 16, 2011 00:22

Adbot: ADBOT LOVES YOU

# ? May 26, 2024 21:48

Orzo: Sep 3, 2004; IT! IT is confusing! Say your goddamn pronouns!

I should have never said megaman, Super Metroid is a much better model for what I'm going for, especially the arbitrary-angled sloped floors aspect.

# ? Dec 16, 2011 00:24

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

«‹›623 »