Natso

Definitions first!

Dead reckoning is the use of previously precise details regarding your location, direction, speed, and other factors which may affect this, in order to determine your current position. Dead reckoning is expected to be inaccurate, as most (if not all) of the data you are working with is not up to date.

Client-side prediction is the use of dead reckoning with application to disguising the lag time inherent to online multiplayer games.


Other considerations:
Smooth position correction, with regards to using dead reckoning for a period, then obtaining new data which would place the character elsewhere.
(He's flying his ship forwards for three seconds on your screen, but in reality he turned after only two seconds of flying straight. Instantly correcting the inaccuracy here may look rather ugly)
Conditional correction, with regards to using highly accurate movement, but much of which is outdated, unless interaction forces more precise positioning.
(You shot the cannon, both clients have an accurate path of projection, and the path shows it will collide with client B. However, client B jumps away at the last moment, so it doesn't actually hit him. The game should favor client B, but we have to patch up the view for client A a bit...)
Acceptable inaccuracy, with regards to details which are trivial or unimportant at different times.
(Movement prediction for your teammates can be a lot more inaccurate than for your enemies, in a FPS. Also, you can change direction by 1~3 degrees without significant difference in real & reckoned position for quite a while.)
Client's recognized position versus server's recognized position, with regards to the client believing an action possible, while the server knows the action is impossible... desynchronization of position & data could become dangerous (with regard to data integrity, etc)
Delta encoding, which is a technique where only data that has changed is updated, and where updates are relative to previous position. (as opposed to updating with precise details)

Lastly, dead reckoning and artificial intelligence (with or without latency considered). For those realistic FPS games, an NPC see's you running behind a tall, but not very long wall. While a human could accurately predict when the running person will be past the wall (and vulnerable to enemy fire), can AI? What if the player could rely on the semi-human instincts of the AI and slow down for a split second before running back out into the open, causing the rocket launcher to miss?

Related links:
Wikipedia Article - Dead Reckoning
Wikipedia Article - Delta Encoding


While most of my examples throughout this post have made reference to FPS, client-side prediction is very applicable in a large variety of common genres, including racing, sports, arcade, RTS, and MMORPG's. Smoothing and dead reckoning can enhance the visual experience, but how much is required, and how much is too much? Also, implementation of correction and prediction is far from simple, in many situations.

Cheers
- Natso

This is just a small collection of scripts that you can use to solve the knapsack problem.

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than a given limit and the total value is as large as possible.

In English:  You have some items of varying weights and prices.  You have a backpack that has can hold up to a certain weight.  You want to put items into your backpack so that your backpack contains the maximum possible price.


A short example on how to use these scripts is shown far below.  The set itself consists of Knap_Init(), Knap_Add(), and Knap_Solve().  Afterwards, an array k_item_take[1 - n] will be generated telling whether or not the item of that index should be taken.

//Knap_Init()
//Dynamic Programming solution of the Knapsack Porblem for Game Maker by Natso
//argument0, size of the knapsack

k_items = 0
k_size = argument0

//Knap_Add()
//Dynamic Programming solution of the Knapsack Porblem for Game Maker by Natso
//argument0, size of the item
//argument1, worth of the item
//argument2, name of the item

k_items+=1
k_item_size[k_items] = argument0
k_item_cost[k_items] = argument1
k_item_name[k_items] = argument2

//Knap_Solve()
//Dynamic Programming solution of the Knapsack Porblem for Game Maker by Natso

k_i = 0
while(k_i <= k_size){
	k_W[k_i,0] = 0
	k_i += 1
}
k_i = 0
while(k_i <= k_items){
	k_W[0,k_i] = 0
	k_i += 1
}

k_i = 1
while(k_i <= k_size){
	k_j = 1
	while(k_j <= k_items){
		if(k_item_size[k_j] <= k_i)
			k_W[k_i,k_j] = max(k_W[k_i,k_j-1],k_item_cost[k_j]+k_W[k_i-k_item_size[k_j],k_j-1])
		else
			k_W[k_i,k_j] = k_W[k_i,k_j-1]
		k_j += 1
	}
	k_i += 1
}

k_i = k_size
k_j = k_items
while(k_j > 0){
	if(k_W[k_i,k_j] == k_W[k_i,k_j-1]){
		k_item_take[k_j] = false
	}else{
		k_item_take[k_j] = true
		k_i -= k_item_size[k_j]
	}
	k_j -= 1
}

That's all the scripts.  I coded it in Java recently, figured I could pull it into GML.

Example Use:

Create an object.

In the create event:

Knap_Init(7)
Knap_Add(3,5,"A")
Knap_Add(2,5,"B")
Knap_Add(3,7,"C")
Knap_Add(2,7,"D")
Knap_Add(2,3,"E")
Knap_Add(1,3,"F")
Knap_Solve()

In the draw event:

draw_set_halign(fa_left)
i = 1
while(i <= k_items){
	if(k_item_take[i] == true)
		draw_text(10,10+(i*15),">"+string(k_item_name[i])+" "+string(k_item_size[i])+" $"+string(k_item_cost[i]))
	else
		draw_text(10,10+(i*15),string(k_item_name[i])+" "+string(k_item_size[i])+" $"+string(k_item_cost[i]))
	i+=1
}
draw_set_halign(fa_right)

i = -1
while(i <= k_size){
	j = -1
	while(j <= k_items){
		if(i == -1)
			draw_text(225+(i*25),30+(j*20),string(j))
		else if(j == -1)
			draw_text(225+(i*25),30+(j*20),string(i))
		else
			draw_text(225+(i*25),30+(j*20),string(k_W[i,j]))
		j+=1
	}
	i+=1
}

Place this object in an empty room of the default size, it should show the matrix it construct, and it will also list the possible items (the items the algorithm says to take are marked with a > in front)


Cheers
- Natso

Actually, this is a quoted portion of an article I wrote, but this is the gist of it.  I think this applies to game developers in general, and being filled with game developers, the GMC would have some applicable comments on this topic.

--
A friend of mine stated "I think gaming in general has hit sort of a writer's block". After some consideration, I find this rather... true.

Consider what is being produced these days. I'll use the top ten recent releases on the IGN homepage as my first example.

-omitted for length-

So, there is a chance that 2 of these 10 recently released games are original. Now lets take a look at some of the top companies. I'll give a rundown on one of my favorites...

[Square Enix]... created Final Fantasy and Chrono Trigger, amongst other games. Earlier this year they released The World Ends With You, definitely an original game (nice too), and last year FF XII (didn't fare as well as previous FF installments, but an original system). They've got at least five potentially original games in the works, three of which are the different parts of the FF XIII set. But let's not overlook at in the past few years they've rereleased Final Fantasy 1, 2, 3, 4 (twice), and 6 (twice), along with Chrono Trigger (for PSX). Next year, Chrono Trigger will be re-released for the second time, for the DS. [That's a lot of remakes]


-omitted for length-

None of these things are original. They've been used and reused in countless games.

The game industry has developed an "originality block" that it doesn't want to overcome. At the dawn of the industry, these genres didn't exist. Every concept was original (or a third-party remake of an original idea), because nothing existed that the games could be compared to.

[Genre rebirth] is occurring. Old genres are finding their place in modern society.

For several years, [shoot'em ups] saw little production. Geometry Wars is one of relatively few shoot'em ups that has been recently produced... the Touhou Project is also noteworthy for its ongoing line of "bullet hell" shoot'em ups that are faring well in Japan.

[Dungeon crawlers and roguelikes]... do you even know what they are? Well, they were primarily made for early computers (one of the more successful was Rogue). Rarely seen on consoles, the genre was dead for a while, but in the last few years this genre has seen a rebirth... notable roguelikes include Pokemon Mystery Dungeon, Izuna: Legend of the Unemployed Ninja, and Baroque, while Etrian Odyssey is a notable dungeon crawler.

[Genre birth] is out of style. The only new genre that comes to mind is...

[Music-based]. Dance Dance Revolution, Guitar Hero, and Rock Band. Stomp and strum along with the music. Our new technology can now facilitate this genre.


Perhaps we have the definition all wrong. Perhaps "game designer" refers to a person who can take old game concepts and hook them up with new storylines, graphics, and sounds. No originality required! Sounds like an easy job, but I'm sure not excited about it.


[Break the modern standards!] As long as developers hide behind their genres, they can rely on the genre's success and playerbase to sell their new games. Read: they WANT to make no progress.


I'm a fan of a development and publishing company called [Atlus]. They regularly break industry norms, creating and localizing games (many of which have been quite successful) such as Riviera(RPG), Yggdra Union(Tactical RPG), and Trauma Center(Simulation). By being a non-conformist, it is producing fresh and quality games that the gamers have never seen before.

The game industry is stuck on [repeat]. Support the companies that are making progress and breaking standards!
--

Entire Article   (digg thanks)

Cheers
- Natso

Because the peripherals required to run this demonstration are not commonly already set up for you to use, I'll give a brief setup in this post.

Required:
GM7, registered (uses 3D)
Some kind of bluetooth link on your computer.  I used a usb bluetooth adapter, cheapest one I could find at walmart (about 20 USD).
A wiimote

Setup:

1. Setting up GlovePIE
Download this program and extract it.
Right-click, Save target as, with this file: HERE
This file is my WiiG'm script for GlovePIE.  Open the script using GlovePIE.

2. Hooking up your wiimote
Open your bluetooth network and the Add New Device window
Press 1&2 at the same time on the wiimote, it should start flashing
Detect, and add, the wiimote to the bluetooth network.

3. Testing your connection
After steps one and two, switch over to your GlovePIE window and run the script by pressing the PLAY button at the top.
You should be able to hold the HOME button down on your wiimote, and the LED's will light up, showing you how much battery is left on the wiimote.
If this does not happen, your wiimote is not connected.  Stop running the script, and return to step two... try connecting it differently.  (it may vary between bluetooth adapter models)

I advise NOT switching windows while running this script!  Your keyboard will seem to produce jargon that could cause problems.  After testing that your wiimote is connected, STOP THIS SCRIPT.

4. Get the script for GM
You can now download my demonstration program in GM.

5. Running the demo
Load the wiigm7.gmk into GM7.  Run the demo now.
Now switch over to GlovePIE and run the script.
Switch the window back to the demo, and you can see the results


The script detects pitch and roll between -90 to 90 in angle, and with approximately 8 degrees accuracy, as well as detecting all arrow keys, A, B, 1, 2, +, and -.

To transmit the pitch and roll, it forces the value to be between -90 and 90, and converts it down into a list of boolean values is a manner similar to binary representation of numbers.  My method is slightly inefficient, but performs its job well enough to be negligible in most games.

This WiiG'm script does not track the acceleration meters in the wiimote.
This script does not utilize the sensor bar or other infared input, and thus cannot track its position relative to the screen.


In the demo, the sword's pitch and roll will adjust to match the wiimotes, and the button icons will light when the corrosponding keys are pressed on the wiimote.  Using Left and Right will rotate the sword along the Y axis.  + and - will zoom in and out.  1 and 2 will restrict pitch and roll when held.


I realize the audience here on the GMC that actually has the tools to do this is rather small.  I don't care to hear comments on this topic!
I also don't care to hear comments about the fact I'm using a secondary program to make this work.  If you don't want to use GlovePIE, don't bother using this demo.  Go find a dll and make it work on your own.
The use of these scripts is rather restricted, so if you make a game utilizing them, don't expect many people to be able to play it.

Cheers,
- Natso

Red is a hard to describe platform game.  It's got a lot of black... yes... a whole lot of black.  And red.

Normal and Survival mode are where the gameplay is found...  In survival mode you will only get a single life.
Also, when you complete the last level, your character will meet an untimely end and you'll be returned to the menu.  Consider it completion, for now (later it will be replaced with a review of your scores, etc)

In this game you'll die a whole lot, I can almost guarantee it.  Learn from each death, and try not to make the same mistake the next time around, and you should be fine

Controls:
Left and Right arrow keys - walk
Up - jump

Download: Here (877 KB)

The game will require focus... and a little bit of repetition.  Just don't make the same mistake twice.

Thoughts?  Please don't spoil in-game elements, though. (This includes screenshots.  They cannot properly show the games atmosphere... so don't post them)

~ This is not a prank/joke game, though I'm sure it may seem to be ~
~ Read user replies for reviews, see for yourself what they think ~

- Natso

edit: updated link 11/20/2008