TedLindstrom.se

Portfolio and blog of Ted Lindstrom, programmer and gamedeveloper

April 8th, 2011

Zeal GS AB recruiting programmer

119 Comments, Bussiness, by tedlindstrom.

Nu söker ZEAL Game Studio AB en “Ambitiös programmerare med bred kompetens” för en projektanställning heltid på 12 månader.

Zeal Game Studio AB är ett företag som är lokaliserat i Visby där ~15 personer är stationerade.
Du kommer vara delaktig i ett av våra projekt som kommer pågå i 12 månader med en bas på 3 programmerare och ca 8 personer i projektgruppen. Möjlighet till vidareanställning finns.

Projektet startar om några veckor så vi ser gärna att du börjar arbeta med oss snarast.

Kompetens
Du kommer arbeta i tirple a-motor och du bör vara mycket bekväm med att programmera i LUA och c++.
Uppgifterna kan variera då gruppen är ganska liten och du måste vara flexibel. Uppgifter kan vara sånna som motorkod, spelkod, nätverkskod, GUIkod och allt annat som innefattar en hel produktion av ett högkvalitativt spel.

Du kommer arbeta i en stark grupp med tydlig ledning men då företaget är litet så ser vi gärna att du är drivkraftig och tillför det lilla extra i alla uppgifter du utför.

Om du känner att du har det vi söker eller snabbt kan utvecklas till det så hör av dig till mig så snabbt som möjligt så ska jag hjälpa dig att komma i ordning och att få känna på våran utvecklingsmiljö innan startskottet för utvecklingstiden avfyras.

Löning
Enligt avtal.

Kontaktuppgifter
NAMN; Ted Lindström
EMAIL: tedlin01@gmail.com
MOB: 0733638679
MSN: swe_typon@hotmail.comTed Lindström

Personligt meddelande

February 8th, 2011

Devdiary: Realtime Shadows

68 Comments, Cause Of War, Dev diary, Programming, by tedlindstrom.

Here’s some screenshots with realtime shadows on soldiers. I also managed to upgrade my previous shadowmaptechnique to always adept the camera representing the light of the sun to fit exactly into the view of the playercamera. It was quiet hard with the current camera being able to rotate 360 degrees in x y and z-axis but now its done :)

Update: Oops, I forgot to render the weapons on 2 previous screenshots so here’s a third ;)

Tags: , , ,

February 4th, 2011

Point inside rectangle test (non-parallel lines)

56 Comments, Programming, by tedlindstrom.

There is many ways for solving this. One is to devide the rectangle into triangles and do a point inside triangle test. But another way is to check wether the point is outside each of the lines of the rectangle.

P : point to test.
A, B, C, D : Rectangle points
DC, DP : Vectors

NOTE: In this example I have already set all the y-coords to 0 since I only need to test in 2D-space. I can’t come up with any other situation where one would need to keep the y-coord.

Psuedo-code:

Vector3 vRectangleCorners[4] = YourCorners, aight.

for(int i=0; i<4; i++)
{
int iNext= i + 1 % 4

// Build the vectors to compare
Vector3 vRecToNext = vRectangleCorners[iNext] – vRectangleCorners[i];
Vector3 vRecToPoint = vPointToTest – vRectangleCorners[i];-

// Normalize to get the directions
vRecToNext = Vec3.Normalize(vRecToNext);
vRecToPoint= Vec3.Normalize(vRecToPoint);

// Cross-product
Vector3 vCrossProduct = Vec3.Cross(vRecToNext, vRecToPoint);

// If vCrossProduct. y > 0 it means that the RecToPoint is left of vRecToPoint, meaning the point is outside of the rectangle
if ( vCrossProduct.y > 0.0f )
{
return false;
}

}
// end loop, and return true becaue the point is inside.
return true;

Tags: , ,

January 17th, 2011

How to grant your VB.Net application administrator privileges under Windows Vista & 7

108 Comments, Programming, by tedlindstrom.

In Visual Studio 2008 you need to add a manifest file. You can do this by entering the properties for the projects and clicking “View UAC Settings” listed under the “Application”-tab.  Now switch the code at line 18 with following

“<requestedExecutionLevel  level=”requireAdministrator” uiAccess=”false” />”

… and that’s it! Enjoy!

Tags: , , , ,

January 14th, 2011

SharpZipLib, Vb.net, Extracting sample with progressbar

58 Comments, Programming, by tedlindstrom.

Dim Stream As ZipInputStream = New ZipInputStream(New FileStream(Application.StartupPath & “\” & inFile, FileMode.Open, FileAccess.Read))
Dim Entry As ZipEntry = Stream.GetNextEntry

progressBar.Value = 0

While Entry IsNot Nothing
progressBar.Maximum += Stream.Length
Entry = Stream.GetNextEntry
End While

Stream.Close()
Stream = New ZipInputStream(New FileStream(Application.StartupPath & “\” & inFile, FileMode.Open, FileAccess.Read))
Entry = Stream.GetNextEntry

While Entry IsNot Nothing
Dim FileName As String = Entry.Name

If FileName <> String.Empty Then
Dim OutFilePath As String = outPath & “/” & FileName
Dim OutDirPath As String = Path.GetDirectoryName(OutFilePath)

If System.IO.Directory.Exists(OutDirPath) = False Then
System.IO.Directory.CreateDirectory(OutDirPath)
End If

If OutFilePath.Last = “/” Then
Entry = Stream.GetNextEntry
Continue While
End If

Dim OutStream As FileStream = New FileStream(OutFilePath, FileMode.Create, FileAccess.Write)
Dim BufferSize As Integer = 2048
Dim DataBuffer(BufferSize) As Byte

While True
BufferSize = Stream.Read(DataBuffer, 0, DataBuffer.Length)
If BufferSize > 0 Then
OutStream.Write(DataBuffer, 0, BufferSize)
Else
Exit While
End If

progressBar.Value += BufferSize
Application.DoEvents()

End While
OutStream.Close()
End If
Entry = Stream.GetNextEntry
End While

Stream.Close()

Tags: , , , , ,

December 26th, 2010

Programming Theory: Shadowmaps, Lightmaps, Ambient Occlusion, Lighting

103 Comments, Programming, by tedlindstrom.

Okey, so you have a game and your artists have done a great job modelling and texturing. What can you do as a programmer? A lot actually! The realistic and and realism looks of the game is highly dependant of the natural lightning of the scene. For it to be natural there is alot of factors to be involved. Some of those that the lighting should come from an direction, it should bounce on objects, it should cast cast shadows and it should shade objects. This is a good start but good start.

Hopefully you already have simple ambient lighting in your game. Perhaps diffuse, normalmaps and specular power also? Now you need shadows to add depth to the scene. I will talk about how I solved it here. Notice that my methods is developed for a static terrain where most objects will never change position and the light always have the same direction.

SSAO
Let’s talk about SSAO, Screen Space Ambient Occlusion. Ambient Occlusion is a techinque that been known for 3d artists for a long time, but  calculating it in realtime is a newly developed technique. It was first implemented in Crysis, year of 2007. Today alot of games use it. Ambient Occlusion is about measuring how crowded an area is. If it’s alot of geometry in a small space, less light would probably reach it. By making use of this one simple rule we can loop through all pixels in the scene and measure the “crowdness” around it and improve the depth of the scene a great deal.
.

If your interessted in implementing SSAO in your game you can read more about this on the internet, because I won’t. In same cases just like in mine this techinque which still is  heavy to calculate can be replaced by simpler techinques. I would say that SSAO is a great thing for a game where there is not very many objects on the scene but in my game there were up to 500 objects on the scene since its a top-down strategy game. Ofcourse one could precalculate the data for each scene if the sunlight would be static but  it would still take a great amount of time to calculate for all these objects. Instead I tried to “simulate” this techinque by just creating a contactsurface towards objects.

Contact Surface



By simply calculating a contact surface in my game I get almost the same results as in SSAO but ~100 times faster.
The first big difference I made towards SSAO was to instead of using an advanced “crowdness-measuring”-techinque I simply sent an ray from the landscape 2 pixels straight up to measure if something was placed right above it. I could do this for each pixel on the landscape, but also for every second pixel or less depending on the resolution I desired. I saved all these information into an 2d array and once everything was calculated i ran through the array and added a PCF-filter to make the shadow blurred and bleed out on the terrain a bit to get it away from the object standing on it. Now were done with the landscapepart, just save the buffer into a texture and load it into the shader and you have yourself an SSAO-looking effect on the landscape.

Next part is to make the objects melt nicely with the landscape. This is done by a very simple trick where I shade the bottom of the mesh in the shader relative to the height of the mesh. This is done by sending the vertexpositions y-coord(not transformed to worldpos) from the pixelprogram to the vertexprogram where I handle it like this ( Color *= saturate(0.5f + VertexAltitude*0.1f) )

Looking nice huh? And it’s very simple to calculate. The far biggest difference between this and SSAO is that in this the objects doesn’t take consideration to each others. It’s just a Landscape-Object relationship, but it’s enough for this type of strategygame in my opinion.
The next part is to make objects cast shadows.

Lightmapping
So you might be thinking about using lightmaps, shadowmaps or shadowvolumes. This part is really tricky to decide but most common ones are lightmaps and shadowmaps. So why do I decide to go with lightmaps?
For different reasons. First off, shadowmaps can be really really tricky to implement since there is over 20-50 techinques and tricks out there to chose from with different beneftins and disadvantages depending on your needs. There is also many obstacles to overcome with shadowmapping (Texturefilters don’t work, limited resolution, Time to calculate, Z-fighting, Penumbra areas and so on),  It can be a pain to get shadowmapping to work dynamically with 99% satisfaction. Another reason for me to go with shadowmaps is that in my case most of the geometry is static so I can simply precompute all of the shadows and fake dynamic shadows for moving objects by attaching a texture on a billboard below it.

So how does lightmapping work?


I have not found very many articles about it and the ones I found have been really complicated. What I do is that I combine two techniques for landscape and objects(if you want shadows on objects).
To create a lightmap for the the landscape I simply send a raytrace from each point(or second, depending on the quality you want) of the landscape towards the direction of the light. If something is blocking that ray then the pixel on the landscape should be shadowed!
Thats the base concept. Really simple, right?
I saved this data to a 2d array, run a PCF filter on it, saved it to a texture and loaded it into the shader. Shadows!

Now you might wan’t to add shadows to the objects also. This could be a little bit more tricky since theyr not geometry isn’t relative to their textures in the same way as the landscape is.
The concept is the same to run through each vertex/pixel on the object and if possible calculate it’s relative texturecoord and by this way save it to a texture. Anyway I had a problem doing this, dunno if i’m to stupid but what I did instead was to save the information into the vertex itself, using the colordata. It was very simple and got a nice smooth look on the mesh, except for those really lowpoly meshes.

That’s it for now! Quite a bit of different from the first picture to the last and since all is precalculated i’ts superast to render :)

Tags: , , , , , , , ,

December 26th, 2010

Programming Theory: Line of Sight, Optimizing Raytracing and intensive collisiontests

95 Comments, Programming, by tedlindstrom.

In the game i’m currently working I have developed a system for allowing high speed updating of Line of Sight and also  a Fog of War to represent the visiblity of the local players line of sight.
I will try to share some of the experience I had developing this, starting out with the realtime updated Line of Sight.

I started out with thinking about the factors I had to keep in mind when designing the system. Some of these factors is that it has to support 2 players with up to 100 interactive objects each. All these objects needs to know if they can see the opponents objects. Some levels has over 500 objects to block the sight, meaning I have to do some superfast raytesting. With a framerate of 60FPS, each frame can take as much as a maximum for 16MS to calculate before the game would start dropping in FPS and the player would notice “lagspikes”.

So what obvious optimizations can we think of?
1.  If I see you, you see me to, right? In most cases yes, it might be some abilities or visiblityfields restricting this rule, but we can add this on later. The first phase of updating the Line of Sight is to do the raytesting and by enforcing this rule we can cut these tests down to the half.
2. In some cases you might not need to know exactly which object can see which object, it might be enought to know if one in the players team can see the other soldier and you don’t need to do more tests on it. This does not work in my case though. I need to know exactly which object each object can see. I some cases one needs to fire upon another and then I can just go and look in earlier collected data if the target acually is in line of sight instead of having to do a new test.
3. One important thing is to not update objects that don’t need to be updated. This can be a bit tricky though when making use of rule 1. For example Obj1 Sees Obj2 and vice versa. Then if Obj1 one moves and needs to update it’s line of sight we must also keep in mind that Obj2 might not see Obj1 anymore. The safe procedures to follow is to keep an boolean in each object to tell if it’s line of sight needs to be updated or not. Once this is changed we need iterate through all objects that sees this object and remove itself from their lists before trying it’s line of sight towards them again.
4. When doing the raytest between two objects to see if another object is blocking the line we might wan’t to think about if we can get the amount of objects to test against down some how. Maybe by checking range, altitude or any other case/state that would remove them from the testing. I will go into this more in detail later on using volumizing.
5. What typ of tests can we do, do we have to do per vertex or is it possible to go for boundingbox or boundingsphere? how about hitboxes? Don’t use more advanced tests then necesarry. Some objects might need per vertex but a house might settle with a boundingboxtest.

These  rules are a couple of those i’m using. They might not fit into your game and you might have oppertunities to use other rules. You have to think of every case of scenario where you can in some how cut down on the amount of raytests. Ask yourself following:  “When do one object NOT need to be testet against?”

The procedures i follow to update the line of sight in my game is as follows:
1.  Make all opponent objects invisible.
2. Run through all objects and check if their line of sight is outdated. If so then remove itself from the LOS-lists of all objects and then do a test again each one of them. If they are spotted then add itself to their list aswell as add them to its own list.
3. Run through the lists of all of my objects and make the opponents visible if their not already visible. Also check for specialcases such as maximumrange, stealth etc etc.

I will know talk about two more general optimizations that will work in almost every case of game and make a huge difference.

Volumizing
When a Raytests is being sent between two objects it means that it might have to test if all objects in the scene is blocking the path. This is totaly unnecessary. There is tons of techniques of cutting down the amount of objects to test against depending on each special case and how optimized it has to be done. Words to google for would be: “Octree”, “Quadtree” and ”Bounding volumes”. I will present my own touch of techniques here:


I simply precalculate a xy-grid( I’m lucky to not have to keep  z-axis in mind in my game) of large boundinboxes covering the whole level. These boundingboxes contains a list of objects located inside the larger boundingbox. Once I do a test I can use these to calculate which meshes I need to test against. This can save a HUGE amount of tests.

Here is a 16×16 grid calculated using VB.net, this is not a complete sample, you will have to figure out where to allocate some variables and such simple stuff by yourself but it will be obvious.

‘ Allocate memory in a 2D array
VolumePrecision = 16  ‘ 16×16
Volume2DArray( VolumePrecision, VolumePrecision )

‘ Compute volumesizes
dim VolumeDepth = LevelDepth / VolumePrecision
dim VolumeWidth = LevelWidth / VolumePrecision

‘ Compute the volumes
For x = 0 to VolumePrecision
For y = 0 to VolymePrecisionThats it for the precomputing part!

‘ This is a simple class, you will understand how to create it.
Dim Obj as cVolumeObject = new cVolumeObject

‘ Compute Volumeboundings
Obj.Min.x = (x * VolumeWidth) – (LandWidth * 0.5F)
Obj.Min.z = (y * volumeDepth) – (LandDepth * 0.5F)
Obj.Min.y = 0

Obj.Max.x = ( (x + 1) * VolumeWidth) – (LandWidth * 0.5F)
Obj.Max.z = ( (y + 1)  * VolumeDepth) – (LandDepth * 0.5F)
Obj.Max.y = 0

‘ Loop through all meshe sin the scene and do a AABB test, you can google this if you don’t know how to.
…. your code
.. if collision accurs add the obect to the volume, for example:
Obj.AddObject( CollidedObject )

Volume2DArray(x,y) = Obj
Next
Next

Now you need to make use of it. This time during runtime. The procedure is to calculate the length between the start and the end destination and then run through the boundingvolumes one by one in the order of the direction, meaning that the probability of a collision is bigger closer to the startingposition and if a collision accurs there, then we don’t have to continue testing beacuse the line of sight is already blocked.

Here’s a sample for the RaytracingFunction in Vb.net

‘ Calculate number of possible volumes to test
Dim LengthVec As Vector2 = StartVec – EndVec
Dim Length As Single = Math.Length(LengthVec)
Dim NumSteps As Integer = 1 + CInt(Length/min(VolumeWidth,VolumeHeight))That’s it!
You will certainly notice a difference in time to do a test.
Here is some results from my tests(big collisiontest for Fog of War based on Line of Sight)

‘ Calculate the direction of the testing
Dim DirVec As Vector2 = LengthVec / NumSteps

‘ Initiate testing
For CurrStep as Integer = 0 To NumSteps

‘ Calculate the arrayposition, this is faster then iterating
Dim x As Integer = CInt((StartVec.x – (CSng(CurrStep) * DirVec.x) * LandWidth * 0.5F) / min(VolumeWidth,VolumeHeight)
Dim y As Integer = CInt((StartVec.y – (CSng(CurrStep) * DirVec.y) * LandDepth * 0.5F) / min(VolumeWidth,VolumeHeight)

Dim E as IEnumerator = VolumeArray2D(x,y)
While(E.MoveNExt())
‘ If collision then we can return, the line of sight is blocked!
…. Your collisiontest here.
If Collision(Start, End)
Return true
End If
End While
End If
Next

‘ If we reach this point then there was nothing plocking the sight
return false

No boundingvolumes: 40 576 MS
24×24 boundingvolumes: 10208 MS
28x28x boundingvolumes: 8064 MS
40x40x boundingvolumes: 8448 MS

Multithreading ( + a little info about my Fog of War )
Okey, another thing that you can do if you like to optimize the line of sight further more or if you wan’t to precalculate a line of sight based Fog of War as i did is to implement Multi threading, it’s really simple using VB.net or pthreads in c++.

For a Fog of War it’s not enought to test the line of sight between opponents, it need’s to be tested against ALL terrain, well it needs to be accurate enought to be pleasent to look at and make use of.
This need’s some heavy precalculation. You can’t update it in realtime, it would drop the FPS to the bottom. The way I solved it was to precompute a 72×72 grid on the landscape of the level and did tests between each of them. This needed tons of optimizations to be pleasent to wait for but It’s another chapter. The point is that I implemented Multithreading here and it saved cut the testresults down from 8000 MS to 5000 MS on my dualcore. It’s almost 50%.

You should really look into it. What you do is that you create a couple of extra threads to run some heavy calculations and in the mainthread you just sleep and lets it wait for all the newly created threads to be completed and then you make use of the data they worked up for you. This is how you should use multithreading, to compute heavy CPU-loaded content. You might accually want to run the Line of Sight updating in a sepate thread for the entire game. I will probably implement that. Then It wont affect the other parts of the game either if it would against all odds cause a lagspike.

That’s all, I hope you learned something. I did when I researched this :)

Tags: , , , , , ,