Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 15 Jun 2006
Offline Last Active Today, 04:12 PM

#5257453 Game of life on GPU question...

Posted by on 16 October 2015 - 02:59 AM

"I need a way to detect this."


Welcome to the "halting problem". (Life patterns are general computers and hence determining their termination falls under the halting problem).


There's no general way to detect these loops -- While two-stage cycles are quite common, you can get three stage... and four stage...


In fact you get N length cycles with a probability of something around 1/N. 


There are also sequences which don't repeat exactly, but also don't produce new information -- the famous "r-pentomino" settles down into a sea of static objects, blinkers and a couple of gliders. The blinkers/statics form a simple loop of 2, but the gliders are more problematic -- while they repeat their internal pattern, they move across the plane so the generations aren't identical.


The good news is that because life is forwardly deterministic, if you see ANY generation you've ever seen before, you know you've entered a loop.


So one simple approach might be to hash your array and keep the hashes. If you see one again, it's a loop.


It won't help you with the gliders... you'll have to get MUCH more creative with them. Note that there is an arbitrarily large set of moving-but-effectively-unchanged objects. Collectively they're call "spaceships" and there's a couple of dozen of them. (There's a catalogue at http://www.conwaylife.com/wiki/Spaceship)


You could measure the expansion of your life frontier (the boundary of live cells) and the count of total live cells. If it steadily increases at a linear rate for more than a certain amount of time, you could conclude that you have a looping system along with a cloud of spaceships moving away from the objects. Spaceships move at known fractions of c -- a glider is c/4 and after 4 cycles it returns to the same number of cells... The problem is that if you have (say) a 5-blinker in your static objects, your loop is now 20 generations, so what you're looking for in that system is a long-term linear trend in the boundary growing at some fraction strictly less than c while the number of cells oscillates through a set of counts (which annoyingly can also be arbitrarily long...)


To emphasise there is NO general purpose solution -- it's demonstrable mathematically for this class of systems that you cannot produce one and trying to will consume periods of time bounded only by your lifespan.


You can get a "good enough for me" solution so aim for that.

#5256332 Tell me the 10? ways to API wisdom

Posted by on 09 October 2015 - 03:29 AM

It's all done with buffers these days. You allocate some blocks of memory and stuff data into them and then point your operation at the buffers and say "GO!".


If you've used 1.2, it's like using the array systems, only you don't allocate the arrays in your program's memory anymore, you just get the API to give you a pointer to the memory.


The other thing is there's no standard pipeline. So you HAVE to use shaders. And that means you have to do the matrix work to produce perspective projections, camera matrices and so on. The disadvantage with this is you have to get everything working at once before you can see any results. TBH, it's easier to go pinch some known working code and go from there because there's a lot of moving parts to all get running.

#5255960 how to follow up on copyrights/patents

Posted by on 07 October 2015 - 01:43 AM

" I could go download a patented font, upload it to dafont.com, and ask $10 dollars for it. "


Well yes, that's one of the problems. People spend ages chasing down infringers like that. And yes, you could theoretically download a font in which someone else has an interest. And yes, they could well wander up to you in a couple of years time and ask for a share of your profits after demonstrating that they're the true owner of the font and hence you used it without a licence...


This is an important lesson -- don't use sites like that. Use sources you can TRUST.

#5255958 how to follow up on copyrights/patents

Posted by on 07 October 2015 - 01:36 AM

My understanding of fonts is the same as Tom's -- using the font is covered in whatever you paid (or agreed to) in order to get hold of it in a form where you could use it to start with. The licence covers the file you load into your editor, not the image of the letters in a given size/colour.


It's the only way it could work really -- after all the original use of fonts is to make a document you print out and give to someone else...

#5255957 Drawing graphics in C++ w/out APIs?

Posted by on 07 October 2015 - 01:31 AM

Your opengl implementation will probably be written in C. It'll communicate with the GL hardware by loading blocks of instructions and data into shared memory. Exactly how to achieve this is often commercially sensitive information -- the various device manufacturers are in competition with each other for speed... and consider the actual hardware APIs to be part of what constitutes their commercial advantage. This is why even the Linux drivers are often opaque code blobs (upsetting purists) instead of readable source.


Why do you want to do this?

Quite apart from anything, getting it working on one card with one kind of GPU won't give you much portability...

#5255617 Is Python good for 2d - 3d games?

Posted by on 05 October 2015 - 02:37 AM

Python isn't the fastest language around so speed-reliant code is difficult to write.


On the other hand, it's certainly fast enough to do the sums involved in moving a few hundred sprite objects around the screen -- one lets the rendering system do all the looping work.


The advantage, from a learning point of view, is that much of the boring fiddly work of who owns which bits of memory is done for you so you can focus on the more interesting parts.


Many of us grew up writing games in a mix of BASIC and assembly language on 8-bit micros, and the kinds of games which worked well there can be written these days in Python much more easily. M&B is, as Sean says, a bit out of reach, but rogue-likes, 2D puzzlers and platformers, shoot-em-ups and so on are within reach (only with better graphics than the 8-bits!). I wouldn't be surprised to find that with a little extra work, things like Starglider could be done in Python these days.


The trick is to design a game that doesn't involve large amounts of data.


Large, of course, means something slightly different these days. A z80 instruction to block copy memory[1] costs 21 cycles per byte copied. You only get 50-100 thousand cycles per 50th second TV field on most 8-bit micros. So you can realistically only copy a few kilobytes of memory per frame..  I had a quick naive play with some code and python on its own is capable of copying 400k per frame. So even in plain old python you've got 100 times as much processing power as we had back in the early 80s...




[1] LDIR, for reference.

#5254849 Could this really be that slow?

Posted by on 30 September 2015 - 12:17 PM

Your code is probably a little naive; brute-force approaches to Life aren't particularly machine optimisable -- the compiler's optimisation won't make much of a dent because there's not a huge set of places to go. It's a simple set of operations run a lot of times and the optimiser can't see far enough to improve them.


There are much faster solutions, but they are algorithmic optimisations. Eg; using a quad-tree to detect "idle" sections of the plane and skip them. Multiple chasing-pointers which can turn the 8 surrounding cell checks into just a couple. (When you come to look at pixel (x,y) you already know 5 out of the 8 cells. You used them for (x-1, y)...)


There are other approaches including run-length encoding the bitmap (reducing the amount of memory accesses needed), sparse grid techniques (Life planes are often sparsely occupied). Dirty rectangle systems, bit-fiddling approaches that can evaluate multiple cells at a time (encode cell neighbour counts in 3 bits and the current state in 1 and now in a 64 bit register you can operate on 16 cells at a time..


You can get away without having a grid at all -- Life plane changes have a speed limit; propagation is 1 cell per generation at most. So not only do you know the cells which might die (the ones which were alive last time), you also know all the cells that might possibly become alive (their neighbours). There are optimisations on these techniques which rely on identifying cells which haven't changed state recently (they're part of a static structure).. you can stop looking at them as well until change propagates out to them.


If you're going to use OpenGL, REALLY use it. You can count the neighbours by taking the current bitmap and adding it into a blank bitmap shifted a pixel in each of the 8 directions... suddenly you're operating on hundreds of cells at a time on the GPU. The life/death decisions is another pixel shader -- and then you can render the bitmap without needing the CPU to do any work at all.


Life is actually a really great way to try out a ton of approaches to optimising :-)

#5254842 How can I make a text parser?

Posted by on 30 September 2015 - 11:57 AM

If this is a part of something bigger, don't reinvent the wheel. Go get a JSON or YAML parser.




1. Toolchains: jq lets you pretty-print and query JSON files. Editors have modes to help you work on the files. There are syntax verifiers and so on.

2. Not finding all the bugs and edge-cases again. Someone's already worked out what to do what you try and put a JSON text into a JSON value..

#5254548 use c# instread of lisp and prolog

Posted by on 29 September 2015 - 01:03 AM

Well, certainly as far as prolog goes unless you've got experience of building a theorem engine, you're missing out on several decades of people developing them. Can't honestly point to a lot of use of prolog in games, but it used to get used a lot in expert systems and does have applications in natural language processing systems.


Part of the power about LISP is that code is data and data is code. That's not true in C# (or any of the languages of that family) where code and data are very separate things. LISP has seen commercial use in games (The "Jak and Daxter" series) and the Emacs editor written in it sees widespread use in the UNIX development world.


If you're going to be a game AI developer, you should very definitely understand why those languages are used where they are much better -- quite apart from any other reason, academic AI research projects are often implemented in them.

#5254272 Game Development as a Career

Posted by on 27 September 2015 - 04:19 PM

"I'm currently attending a community college in the Virgin Islands and it doesn't benefit me too much. "


Yes it does. It's teaching you to stick at things.


If you're going to stop going, stop going. Tomorrow. How can you be thinking about maybe not finishing college at some point in the future? Make a bloody decision!! If you're going to quit, quit. Start looking for a job at 9am tomorrow morning.


If you're not going to quit, go and ace that VB course -- and I mean, be first in the class. And get working in your spare time as well.


"i'll look for a job"


What, as a college drop-out? Well, you're certainly reducing the number of exciting opportunities you'll be forced to choose between. Quite apart from not graduating, dropping out of college is a bad way to start a CV. Says you can't stick at things.


You don't need online courses to learn languages or games development. Frankly they're just not information dense enough. Why? Because they have to run at the speed of the thickest person in their audience. The thickest person in their audience won't ever get hired as a games developer. If you're going to succeed you need to move faster than that. Get reading textbooks. Get writing software. If you want to be a software developer, act like you're interested in it. Have you written any games? Why not?

#5251133 Generating and initializing content for a text RPG

Posted by on 08 September 2015 - 04:23 AM

SQLite could be quite an interesting solution. It's a single library you link to your C++ binary and lets you run SQL at a database which lives in a single file.


You could therefore write an SQL script which sets up the database as part of your build process.


The player "starting" the game then means that your app just copies the original master datafile and opens the copy for the player to work with. "Saving" the game consists of closing the SQL connection (to make sure all the changes are committed) and copying the file and reopening the SQL connection and then carrying on.


One of the interesting aspects of this is that can manipulate the database "behind the scenes" to help you debug it; because you can just open it in another SQL session and query what happened to those objects when you ran that command.

#5248722 Legal dangers for small indies

Posted by on 25 August 2015 - 03:58 AM

You don't need to worry about this until you have a saleable game product.


Artwork can always be swapped out later.


Develop complete game-play which people like before worrying about legal structures to sell it.

#5247343 Food for aliens

Posted by on 18 August 2015 - 03:21 AM

"who knows what might happen?"


Hehehehe. That was EXACTLY the clip I thought of as well :-)



Seriously though; there's decent evidence that amino acids (what we need proteins for) and sugars are pretty common chemicals and can even form naturally in chemical clouds in space in quantities we can detect from a thousand ly away. Conway Morris argues in a couple of his books that this would imply alien life a) will exist (because the materials are readily available) and b) will be made of much the same sort of stuff as us, and presumably therefore will have similar basic dietary needs.


Note, however, that even on earth many life-forms are incredibly intolerant of even small changes to their diet. Pandas live on particular species of bamboo and won't eat anything else. Sheep can be poisoned by being moved to fields with grass they're not used to... apparently they're very sensitive to trace metals contents.


So while it might be possible to synthesise the right foods from materials, the actual food isn't likely to be very portable.

#5246177 Visual Effect: Possible to "Split/Explode a sprite into rows" using a...

Posted by on 13 August 2015 - 05:26 AM

This would seem like an ideal job for a pixel shader. You're (presumably) drawing a rect with some sub-area of a texture mapped onto it. The pixel shader runs for each pixel in the image and can fairly easily detect if this pixel is on a row or column which should be left blank, in which case it simply returns a completely transparent pixel -- essentially instead of scaling the texture patch to fit, it just.. breaks it up.


If you think about it in one dimension to start with (because extending it to two is easy once it's working), you want to skip N-1 pixels when the image is N times larger than the original. And you want to do this in texture coords (because you may already be stretching the image to get (say) a 32p wide image to draw onto a 128p wide screen area. So if you ask for a draw onto a 256p wide area, you want the pixels to be XXXX----XXXX---- not X-X-X-X-...


So, all you need to know is the "shatter" scaling (2 in the case of above; and it can be a floating number). Take the fractional (sub-pixel) part of your texture coord. Multiply it by the shatter scaling and if the result is >1.0, this pixel should be transparent. ExReader: use sprite-centred coordinates so that the shatter effect is symmetrical...


I'd suggest having a play around with a basic shader to start with though -- say getting your sprites to appear in monochrome or some other simple processing as a learning exercise -- then work up to something that needs a bit more juggling.

#5220883 VAT/Sales Tax, Incorporating, Changing DBA, And More

Posted by on 02 April 2015 - 04:06 AM

Go and write the game. Don't worry about any of this stuff.


When your game is complete and ready for sale -- or even just ready enough that you're considering investing in hiring some contractors -- then you can go hire a lawyer for two hours to sort all this out for you.


Write a good game, worry about selling it when it works.