next »

[Tycho Brahe]

Wow, I've been using something just like this and I hadn't realised it was so special...

[dbb]

Wow, I've been using something just like this and I hadn't realised it was so special...

Yeah, last time I tried building a platformer in Game Maker I had an algorithm analagous to this to have the camera smoothly track the main character. Weird thing is, I would generally descibe myself as completely ignorant about both programming and maths. I just stumbled across this solution because I had a very clear definition in my head of what I wanted the camera to do, I guess.

[Tycho Brahe]

yeah, ages ago I made a (very) crappy flash game, where all the enemies moved that way...

[rogerlevy]

I'm designing and implementing my very own weak-typing/oop system for Forth.  It works by recursively looking up a keyword's type (or an implicit type) as a prefix added to a word, so "object.action" becomes "type.action" and the second word is what is actually compiled.  makes it easy to test these words on the commandline.  also gets many of the benefits of oop because basically you are writing methods and using inheritance, but there isn't any overhead in the compiled code.  i think this is how C++ works...

[Zaphos]

It turns out that numerical solutions to Laplace's equation (del squared phi equals zero) are very easy to code.

phi_i,j = (phi_i+1,j+phi_i-1,j+phi_i,j+1+phi_i,j-1)/4

Repeat until phi doesn't change much. I've played with this algorithm before just for fun, but I didn't realize it could be applied to solve real problems.

This is a specific case of a general method for solving a linear system, where you just iteratively satisfy each row of the system -- if you overwrite values as you go, it's called the Gauss Seidel method; otherwise, it's called the Jacobi method.

If you're willing to generalize a bit, the idea shows up all over the place -- in resolving collisions for a simulation, you'll often see people go to each collision and locally resolve it, iterate a few times, and hope the system converges to a globally valid state.  And for doing inverse kinematics with the simple "Cyclic Coordinate Descent" method, you go to each joint in order, solve for the locally best angle at that joint assuming none of the others move, and repeat until convergence.

It's usually not the most efficient solution, but it's easy to code and understand and often works surprisingly well

[st33d]

BUMP

L-Systems

First off - the great book The Algorithmic Beauty of Plants can be downloaded as a pdf here:

http://algorithmicbotany.org/papers/#abop

It will tell you all the basics of L-Systems and so much more.

Here's an old L-System applet of mine - click on it to regrow trees:

http://www.robotacid.com/PBeta/burst/index.html

But you can also use L-Systems for paths and AI. I used a rather complex form of L-System to instruct monsters how to behave in Fat Cat and in this next art game, the monsters randomly generate paths to seek you with. Successful monsters are saved to your shared object - meaning that the game eventually learns to be impossible to play:

http://www.robotacid.com/flash/provocation/index.html

(Not the best game I know, but the research has its uses and it's open sauce. And no, I'm too busy with Red Rogue to apply any criticism.)

Mostly I use L-System type data nowadays to store map tile information. Meaning that I can pack some pretty nifty behaviour into a monster and when he goes off screen - retain new data as he is converted back into simple map data.

This generally means I rag the hell out of RegEx sometimes (often you can get by with lastIndexOf and such, but when you nest instructions in brackets, RegEx is useful).

So here's a free RegEx tool:

http://www.gskinner.com/RegExr/

and here's the downloadable Air app version:

http://www.gskinner.com/RegExr/desktop/

[st33d]

Found this paper on HPA*

http://webdocs.cs.ualberta.ca/~mmueller/ps/hpastar.pdf

It's a faster version of A* that sacrifices a little accuracy by abstracting the larger search into a set of zones. So you basically do A* on a small map to the zone exits for where you are, do a search on the big zone map, then dive down into the small map to finish the job.

[skyy]

L-systems reminded me of this old demo from Assembly:



Mint :3 keep looking and the L-system fractal plants will pop up.

[st33d]

Just found out about N-Grams today from reading Artificial Intelligence for Games by Ian Millington.

Given a sequence like the player's movement you can use the N-Gram set up to determine the probability of what they'll do next and act on it.

Quite the obvious route really, but I didn't know there was a name for it. And now I'm wishing I was making something that could use it.

[nikki]

And now I'm wishing I was making something that could use it.

that sounds like an healthy fetisj 

[d3sphil]

Started going through Type Theory & Functional Programming (by Simon Thompson) today.  I've never read up properly on (CS) type-theory before.  Really enjoying the presentation in that text, and the content.

Huh.. I'm amazed that some people here actually read up on this stuff/find it interesting. This is the kind of stuff I do on a daily basis. You should also check out Robert Harper's book http://www.cs.cmu.edu/~rwh/plbook/book.pdf, he is one of the co-authors of SML.

[Crimsontide]

One of my favorite algorithms is the CORDIC algorithm:

http://en.wikipedia.org/wiki/CORDIC

I used it to implement basic trig functions for a fixed point math library I wrote.  What's neat is despite it being fairly math-heavy from an understanding/formulation point of view, the implementation was so simple, quick and easy it was amazing.


Another one I stumbled on a while back was using a neural net for palette reduction:

http://members.ozemail.com.au/~dekker/NeuQuant.pdf

I had played with a number of palette reduction methods, and this one beat every other method both in speed, memory usage, and quality by such a large margin it blew me away.  The 1st time I implemented it I thought it didn't work as the resulting image was so good I couldn't visually tell it had actually reduced the colors on the image (and I had picked images that were hard to reduce on purpose).

[increpare]

This is the kind of stuff I do on a daily basis.

Cool! :D

You should also check out Robert Harper's book http://www.cs.cmu.edu/~rwh/plbook/book.pdf, he is one of the co-authors of SML.

I'll give it a look - might make for some good compile-time reading material  : )