Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length

 
Advanced search

1384988 Posts in 66307 Topics- by 58780 Members - Latest Member: masendor

November 23, 2020, 07:24:49 PM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsDeveloperTechnical (Moderator: ThemsAllTook)Interesting Programming Problems
Pages: [1] 2
Print
Author Topic: Interesting Programming Problems  (Read 2995 times)
jeffrobot
Level 1
*



View Profile
« on: August 16, 2011, 01:01:21 AM »

Hey guys, I'm always coming into the Technical subforum, hoping someone is posting about an interesting problem they have or feature they're trying to implement. It is my hope that I can learn a new technique, or how to implement a cool feature in a game of my own. However, that rarely happens : (

So here's a thread where we can all discuss ways we would solve various problems and implement various features.

I've always been curious how radars in FPS's work. Then I thought about it recently, and feel like I've begun to reach some answer.

I would have a coordinate system that tracked distances between all the relevant objects in the level. Then, I would use the proportions of those distances to plot the distances in miniature in the radar!

Wow, so simple. Can't believe I never thought of that before.

Who's got another one?
Logged
Sanojian
Level 1
*



View Profile
« Reply #1 on: August 16, 2011, 03:17:18 AM »

I am messing around with network programming and I need a way to hide latency.  Right now I am just fudging it by tweening the character to the correct position on every location update, but the results are pretty horrific.  The other players look like Bambi on ice.  This is a 2D isometric game.

I have punted on this issue before by making my players move more slowly. Not surprisingly this non-solution resulted in unhappy players.

I am going to try the solution suggested here: http://www.mine-control.com/zack/timesync/timesync.html

Does this interest anybody?  If so I will report back here when I have implemented it. 
Logged

sublinimal
Level 8
***



View Profile
« Reply #2 on: August 16, 2011, 03:29:05 AM »

I find the concept of raycasting ingenious. But I might just be easily impressed and ignorant of any slightly advanced math.
Logged
Mikademus
Level 10
*****


The Magical Owl


View Profile
« Reply #3 on: August 16, 2011, 04:53:32 AM »

@Sanojian, network latency and entity position correction is a very interesting problem, so yeah, post back your findings! Also, that article was interesting and the technique employed seems solid.
Logged

\\\"There\\\'s a tendency among the press to attribute the creation of a game to a single person,\\\" says Warren Spector, creator of Thief and Deus Ex. --IGN<br />My compilation of game engines for indies
braindigitalis
Level 1
*

Making games for the fun of it since 1993


View Profile WWW
« Reply #4 on: August 16, 2011, 05:29:08 AM »

Hey guys, I'm always coming into the Technical subforum, hoping someone is posting about an interesting problem they have or feature they're trying to implement. It is my hope that I can learn a new technique, or how to implement a cool feature in a game of my own. However, that rarely happens : (

So here's a thread where we can all discuss ways we would solve various problems and implement various features.

I've always been curious how radars in FPS's work. Then I thought about it recently, and feel like I've begun to reach some answer.

I would have a coordinate system that tracked distances between all the relevant objects in the level. Then, I would use the proportions of those distances to plot the distances in miniature in the radar!

Wow, so simple. Can't believe I never thought of that before.

Who's got another one?

I remember trying to write a radar system like this once and as i remember my solution was quite simple. For all nearby enemies i calculated distance along the X/Y plane using pythagoras to determine how far away it was and then used atan2 to calcualte the angle, i then plotted its distance scaled to a circle which formed the radar. This didn't take into account height difference between that enemy and the player, but i guess such a thing would be simple to do.
Logged

Mr Boom's Firework Factory - Released Summer 2019
TriviaBot Discord Trivia Bot - Available Now
Nix
Guest
« Reply #5 on: August 16, 2011, 07:28:50 AM »

I've had to solve a lot of really fun programming problems for Solar Reboot. The biggest one (and arguably the most important one to game because it's part of the core mechanic) is a way to perform geometric light casting. I couldn't use plain old shadow casting shortcuts where you project the shapes of shadowed objects outwards. I had to develop a way of truly casting the *light* outwards, and then allowing it to be manipulated by modifiers in the scene like mirrors, refraction, etc. I haven't written anything up about it, and I probably won't until I'm done with the game, but here's a video: http://solarreboot.blogspot.com/2011/01/first-look-mirror-demo.html

It took a lot of trial and error and revision and a fair amount of trigonometry and some linear algebra, but the final technique I developed is pretty simple. There is still a lot of room for optimization because I brute forced quite a few of the sub-calculations. I haven't studied computational geometry much though, so I haven't put in the time researching existing algorithms that might speed up some of the raycasting, etc.

Another cool thing I did for this game, though not nearly as involved, was using perlin noise to create moving edge effects for the lights. Here's a video of that: http://www.youtube.com/isaac24321#p/a/u/0/oC1pIZVpofU
Logged
Evan Balster
Level 10
*****


I live in this head.


View Profile WWW
« Reply #6 on: August 17, 2011, 10:27:03 AM »

I don't know where to start.  :D

I've done raycasts and lightcasting in 2D polygon space (non-sample-based -- Nix, if you're using raycasts and getting "poppy" changes I can tell you about the algorithm, though it's not as trivial with things like mirrors) and now I'm working on an especially crazy data structure I need for several things.


Polygon space partitioning.  Essentially it's a bit like a 2D mesh composed of polylines that join at "nodes" to separate spatial regions from one another, which can be modified only by making either "cuts" (and splitting away all completely independent spaces) or "dropping" regions over existing parts of the map.  This system can't allow complex (self-intersecting) polygons and has to deal with all the possible closet cases, since it needs to take hand-drawn input from a vector painting tool and randomly generated cuts for things such as procedural shattering effects.

(If you're having trouble envisioning it, think of a map of countries and oceans divided by borders.  Seas or other countries can exist entirely inside other countries, and borders can't overlap other borders.)

So far I've implemented an algorithm to perform the simple task of recursively searching the map for which region (including an infinite "exterior" one) and a system of structuring the map into "clusters" of connected lines and the regions they encompass, with "child" clusters being those clusters which lie entirely within another region.  I've also written a specialized raycast which geometrically defines the epsilons around lines as an ovaloid (round-ended line) shape and picks up on degenerate cases like colliding with vertices and nodes.  I'm hoping that epiphany will prevent horrible inconsistent state bugs from cropping up and ruining my fun.

What I have yet to do, having shelved this system for a while, is write the procedure for actually dividing the space based on all these intersections.  I need to convert "piles" of edge-lapping shapes into this new format for Infinite Blank, so it needs to specially handle cases where a "cut" runs entirely along the length of an existing border, or along part of it with divergences.  Cuts can be lines or loops, and can join child regions with parent regions, but only if two polylines are created joining them.  Also there needs to be support for multiple simultaneous cuts even though the data structure will NOT store lines that don't have the effect of fully distinguishing a shape.  (Though I'm reconsidering this last part)  All modifications will return a mapping from old polygon regions to new ones created by the division.

I shelved this work a while ago but it's getting relevant again as my current project could also use a shattering effect and I want to get back on Infinite Blank.


I've realized that with the addition of a near-trivial operation for "erasing" polylines to merge shapes, this system could be used as a full-featured CSG engine.  Though I can't imagine it'd be nearly as efficient as the fabulous free one I use now.
Logged

Creativity births expression.  Curiosity births exploration.
Our work is as soil to these seeds; our art is what grows from them...


Wreath, SoundSelf, Infinite Blank, Cave Story+, <plaid/audio>
moi
Level 10
*****


DILF SANTA


View Profile WWW
« Reply #7 on: August 17, 2011, 10:58:33 AM »

 say you have a simple arena-type of game (think dual stick shooter)
you have a swarm of enemies that constantly follow the player according to an algorythm
How do you prevent the fact that after a while (after the player moves and turns around the enemies for several seconds), all the enemies end up on the same location and following the same path to the player? ending in only one enemy sprite on scren (actually severl dozen sprites all stacked at the same location)

I've tried several fixes including making the enemies bump into each other and randomizing the path, but somehow none of them is really satisfying.
Logged

subsystems   subsystems   subsystems
DeadPixel
Level 2
**



View Profile WWW
« Reply #8 on: August 17, 2011, 11:07:47 AM »

say you have a simple arena-type of game (think dual stick shooter)
you have a swarm of enemies that constantly follow the player according to an algorythm
How do you prevent the fact that after a while (after the player moves and turns around the enemies for several seconds), all the enemies end up on the same location and following the same path to the player? ending in only one enemy sprite on scren (actually severl dozen sprites all stacked at the same location)

I've tried several fixes including making the enemies bump into each other and randomizing the path, but somehow none of them is really satisfying.

You may have already gone down this route but consider implementing steering behaviors for your AI entities.  In particular flocking + wander behaviors should give you decent results.  This will give you an organic sense of flow with your swarm as well as randomness.
Logged

Mikademus
Level 10
*****


The Magical Owl


View Profile
« Reply #9 on: August 17, 2011, 11:09:40 AM »

Moi, what you want might be a flocking algorithm. The player attracts the enemies. Enemies repels each other. And some enemies are attracted to the future extrapolated position of the player rather than his current one.
Logged

\\\"There\\\'s a tendency among the press to attribute the creation of a game to a single person,\\\" says Warren Spector, creator of Thief and Deus Ex. --IGN<br />My compilation of game engines for indies
TheLastBanana
Level 9
****



View Profile WWW
« Reply #10 on: August 17, 2011, 02:37:13 PM »

I've been having some fun recently making a system that automatically chooses a tile's sprite based on its surroundings. My artist (capnbubs) gave me a sprite sheet to work with and I thought this would be a neat project. It's lots of fun to platy with now that it's working!
It sounds simple, but it really isn't! The complicated part is that, to make things look nice, some of the tiles are made up of a solid ground tile, then a small, rounded patch of dirt on top. I ended up coming up with a method of defining each tile and when it'll appear, as well as what tiles it'll add. On top of that, some tiles need to add multiple generations of tiles (mostly for the background - you add one tile, it adds 8 more tiles, then those tiles each add some tiles). But all of those tiles need to interact differently depending on how many ancestor tiles they have, so I added a "generation" system to the whole thing. Different tile types also need different layers, too, like the aforementioned background, or grass growing on top of the dirt.
After a bunch of work, though, it's working pretty nicely:

I can just define the shape of the terrain, like so:
http://dl.dropbox.com/u/2149322/TileEditor/Ground0.png

Then it places all the dirt looking nice and interconnected, as well as automatically adding background tiles:
http://dl.dropbox.com/u/2149322/TileEditor/Ground1.png

If I want to, I can just switch layers and put some grass on top:
http://dl.dropbox.com/u/2149322/TileEditor/Ground2.png

As well, since I made all the tiles dynamically connectable, you can extend the background beyond its default placement if you want to! Take these tiles, for instance:
http://dl.dropbox.com/u/2149322/TileEditor/BG0.png

I switch to the background layer and drag out a shape:
http://dl.dropbox.com/u/2149322/TileEditor/BG1.png

And the result is a fully-connected background!
http://dl.dropbox.com/u/2149322/TileEditor/BG2.png

All of this tile data is being read from a human-readable, 37-KB text file (although it's growing rapidly).
« Last Edit: August 18, 2011, 11:06:31 AM by TheLastBanana » Logged
baconman
Level 10
*****


Design Guru


View Profile WWW
« Reply #11 on: August 18, 2011, 07:20:27 AM »

say you have a simple arena-type of game (think dual stick shooter)
you have a swarm of enemies that constantly follow the player according to an algorythm
How do you prevent the fact that after a while (after the player moves and turns around the enemies for several seconds), all the enemies end up on the same location and following the same path to the player? ending in only one enemy sprite on scren (actually severl dozen sprites all stacked at the same location)

I've tried several fixes including making the enemies bump into each other and randomizing the path, but somehow none of them is really satisfying.

Parent the main object, and create a set of child objects; one that homes in North of the player, another South of the player, a couple more East and West, and then maybe a couple that take totally different approaches. Like providing cover fire for other enemies; aiming at points -around- the player instead of directly at them to hinder their mobility; avoiding the player's line of sight/fire and attacking with grenades, taking bank shots, or setting traps/explosives. Of course, nothing wrong with including a random dummy one too - their unpredicatability adds a lot to the experience, and so does having an easily-squashed foe type.
Logged

moi
Level 10
*****


DILF SANTA


View Profile WWW
« Reply #12 on: August 18, 2011, 07:54:32 AM »

thanks for the suggestions guys
Logged

subsystems   subsystems   subsystems
Evan Balster
Level 10
*****


I live in this head.


View Profile WWW
« Reply #13 on: August 18, 2011, 09:00:46 AM »

TheLastBanana -- cool system!  Check your links though; the last one was supposed to be this:

Logged

Creativity births expression.  Curiosity births exploration.
Our work is as soil to these seeds; our art is what grows from them...


Wreath, SoundSelf, Infinite Blank, Cave Story+, <plaid/audio>
TheLastBanana
Level 9
****



View Profile WWW
« Reply #14 on: August 18, 2011, 11:06:58 AM »

Oops, yup, thanks for catching that.
Logged
lasttea999
Level 2
**


View Profile
« Reply #15 on: August 18, 2011, 02:52:40 PM »

@TheLastBanana: I've been interested in this sort of problem. I wonder if there could be a thread dedicated to discussing that topic; I'm thinking there are many different ways to address the issue!
Logged

TheLastBanana
Level 9
****



View Profile WWW
« Reply #16 on: August 18, 2011, 03:10:11 PM »

Sure, that sounds great! I'd be willing to share some of the inner workings of my system. I'll come by later and talk about it a bit if you've set the topic up (or if not, I'll just start the topic) - I'm working on some other parts of the system at the moment. Wink
Logged
nahkranoth
Level 2
**


View Profile
« Reply #17 on: August 18, 2011, 03:17:41 PM »

I wanted the worms style Bitmap Level Damage. But i wanted surten materials to be stronger then others. So that steel would survive longer then concrete, etc.

So i made a health (tile) graphic for every material and for every stronger one i made it a lighter shade of gray. Then, for every impact of a bullet i plot a circle on top of the level bitmap that has a transparancy. After that i check every pixel of the impact area of the level bitmap to see if it is totally black, 0x000000 type o' black,  Ninja Because of the transparancy, darker pixels will go black sooner then lighter ones and every impact circle plotted on top of another adds up till it finally is black enough and is erased.

If it is black i will make it transparant. This health graphic is masking the level bitmap und...  Wizard taaahdaah! we have ourselfs a problem solved. Gentleman
« Last Edit: August 18, 2011, 03:25:37 PM by nahkranoth » Logged
zovirl
Level 1
*


Mark Ivey


View Profile WWW
« Reply #18 on: August 19, 2011, 09:00:47 PM »

Something that was trickier than I expected was getting a "chunking" algorithm for loading level data in a side-scrolling game. Basically I don't want to load the whole level at once, only the areas next to where the player currently is.

The terrain in the game is defined by a series of points (using interpolation to fill in between the points). What got tricky was that the placement of the terrain points is arbitrary so they don't line up with the chunk boundaries. Trying to figure out how to interpolate between points where point A is in one chunk and point B is in the adjacent chunk ended up getting complicated. It was difficult to figure out which sectors contained the needed data.

I ended up storing 2 extra terrain points in each chunk: 1 to the left of the chunk and one to the right.  This way each chunk contains enough data to interpolate the terrain right up to the edge of the chunk.
Logged

Alaskan Runway, a side-scrolling flight sim I'm working on.
Forest, a walking meditation game. (behind the scenes)
www.zovirl.com
jeffrobot
Level 1
*



View Profile
« Reply #19 on: August 20, 2011, 06:04:55 PM »

I wanted the worms style Bitmap Level Damage. But i wanted surten materials to be stronger then others. So that steel would survive longer then concrete, etc.

So i made a health (tile) graphic for every material and for every stronger one i made it a lighter shade of gray. Then, for every impact of a bullet i plot a circle on top of the level bitmap that has a transparancy. After that i check every pixel of the impact area of the level bitmap to see if it is totally black, 0x000000 type o' black,  Ninja Because of the transparancy, darker pixels will go black sooner then lighter ones and every impact circle plotted on top of another adds up till it finally is black enough and is erased.

If it is black i will make it transparant. This health graphic is masking the level bitmap und...  Wizard taaahdaah! we have ourselfs a problem solved. Gentleman

That's pretty tricky, very cool. I've never thought of using graphical techniques in my programming like that. Something to keep in mind...
Logged
Pages: [1] 2
Print
Jump to:  

Theme orange-lt created by panic