[shuffle]

Of course, there is a better way to do this that avoids infinite runtime...

For a relatively small set of potential objects, rather than just randomly picking one, you can shuffle the entire set. There's quite a few ways to do this, from ways that mimic how one might shuffle cards, to the rather quirky approach where you assign each element in the list a random number, then just sort according to the random number!

I think BorisTheBrave has been spot-on here. Bitshifting and endianness might be the most many people see of the underlying architecture, but when I hear "low level", I think about the entire implementation.

If you are coding less performance constrained games, then no, this sort of thing isn't important. But if performance is an issue, and especially if you are writing code for microcontrollers, you really need to understand the low-level details.

Without knowing more about the position you have an interview for, it is hard to offer better advice. However I would recommend to anyone that it is worth getting some experience working down at machine level, coding for a microcontroller. Knowing the concepts of assembler, what pointers really are, and how virtual memory works are things worth knowing, and having to work around a limited instruction set and other resources (such as memory - imagine having only a kilobyte or so; or processing speed) is very empowering in the long run.

To be honest, I think you are complicating things by calling the second variable 'weight', rather than the more standard "estimated cost to goal". This gets especially important when each move can have it's own cost, since people often use cost and weight interchangeably in pathfinding.

In particular, it is important that this variable only contain probable values, not known ones - so I found it a bit strange that you added the known danger of the cell to this, rather than the cost. Further, you seem to be only adding the danger of that cell, rather than the estimated total danger remaining.

Other than that, it's a good tutorial, I think. You might want to extend it with details on minimising the returned route (see the gamasutra links in the other thread).

From what I can tell, your problem is specifically coming from your use of a tiled grid, when the objects placed into your world are not constrained to the same grid.

There are two solutions that I can see:

Firstly, the less interesting one - simply use a finer grid size. However, as you point out, this could impact performance.

Secondly, don't use a regular grid. This requires some pre-processing time, but generate a series of nodes that are between the circles and that have enough clearance around them to allow passage. Once the initial system has been generated, it should then be possible to dynamically update this if required. The end of this gamasutra article discusses some options, and it should be relatively trivial to search for more information

On a related note, also see this other gamasutra article, which I consider essential reading for pathfinding algorithm design. Being able to minimise the route and make it more realistic is rather awesome

[good]

Loads of ways you can do it, but one piece of advice quickly: if it sounds CPU taxing, then let that thought go and implement it anyway. The chances are it will be fine - and if it isn't, you can probably optimise it. Never let FUD get in the way of doing something correctly. Then again if you're implementing a brute-force algorithm you may be doing it wrong!

Haha, yeah, I tend to do that a lot, I guess it's a bad habit of mine :D

good habit If something seems probably CPU taxing, but you can't immediately see what to do about that which would work to fix it, then just move on. A yet-to-be-implemented required feature is always a bigger performance hit than non-obvious optomisations

The only problem I can really see with your method is that it's not generic In effect, you are manually checking six of the nine possible collision tiles (you missed the centre column, but that's not a problem if you can guarantee safe sprite placement and sub-tile movement distances), taking these positions manually and hard-coding them, rather than working them out from the bounding box.

Move the rectangle in tiny increments along its velocity until it hits something.

If you can guarantee that your movement per tick will always be less than the minimum size for a collision object, there is a much better way to do this step.

Rather than incrementally searching each and every step, perform a binary search. Check half way along, then halfway along the known partially clear section, and so on. Generally, this would mean having to perform far fewer collision tests, and so give better performance.

As noted, this would not work if it is possible for your collision objects to be moving so fast to pop out the other side of each other. For these cases, collision systems generally use different formulae.

In a way, collision handling itself often results in two different systems - one for pure physics collisions (where you simply alter the velocity according to the physics of the interaction), and one for AI that may chose a different path after colliding.

at a quick guess, is your loop correcting for the increased time it will take to complete the loop as you add more boxes?

[discrete modes of action]

Woah, that's a big and complex AI project you have there! Have you much experience with coding AIs?

Like with any problem, a good place to start is to break it right the way down. Identify the core elements, and see if you can simplify it at all. In your case, we can see that:

• 1. There are entities
• 2. Entities can 'see' other objects within a field of vision
• 3. Entities can determine ('observing') properties of objects they 'see'
• 4. Entities 'Seeing' objects and 'observing' properties on said objects store some knowledge regarding these
• 5. Entities may 'observe' for varying lengths of time, based upon some control variables

Looking at this list, there are two things strike me. Firstly, you haven't given any indication as to the purpose of item 4, but presumably this would effect the control variables. Secondly, there are discrete modes of action for the Entity. This strongly suggests that the core of the entity could well be a finite state machine.

The control variables can be polled to determine state changes. To make things a little more fuzzy and realistic, you can compare the control variables against a random number. The control variables themselves can be of whatever level of complexity you desire, and could even be used as the input and output of a neural network, if so desired.

I'm not entirely sure that a neural network would be the best solution. It seems to me that the entities are effectively building up a list of rules, and how true they have found these rules to be ('certainty factors', to give the formal name). I would personally consider a different form of machine learning, and might try to use the Naïve Bayes classification formula.

You could also use a singleton resource manager.

In my engine, i have a general Services singleton that provides "global" access to a lot of the static engine pieces like the renderer, OS core and various manager class subsystems.

...Or you could avoid the evils of singletons, and simply pass the resource manager as a parameter to the constructors of all classes that need it Looks a bit more messy, but the factory pattern can be used to hide most of it, and it significantly helps in testing and code reuse.

A few years back, I asked a number of professionals about this, and the general agreement was that building up reputation and networks using your real name is a good thing. So here I am Being google-able is probably a good thing, all things told.

I also maintain a professional-yet-somewhat-anonymous username, and some other ones that I'm telling no-one about and can't be linked to me. What's professional stays professional, and what's silly stays far away from work.

When it comes to publishing games and software, I would however recommend publishing under a company name, so as to allow you to more easily get other people involved yet still keep a unified branding.

Parsing the bitmap into a convex polygon would help. Line-line collision testing is almost certainly going to be less intensive than bitmap scanning. The important thing here is simply to use this to reduce the workload - you simply need the generated polygon(s) to be guaranteed to fully enclose all collidable pixels. Depending upon how you are running the simulation, there are a number of techniques which could be used to do this (for example, a simple collision grid).

After this, I don't think there is any escaping iterating through the underlying pixels themselves. If you don't want to make an exact polygon representation, I can't really see any alternative. However, there are some tricks you can use for speed.

Firstly, ensure that all the colliding areas are continuous. If you must have separated regions, make these further apart than the size of the colliding bodies, such that you need only consider the pixels along the edges when checking the bitmap for collision. Similarly, objects should move at a slow enough speed such that they don't pass right through a section of the collidable bitmap before the next collision check.

The bitmap itself should ideally be literally a bitmap, allowing simple sequential bitwise operations to check for collision.

Your main issue when checking the bitmap is going to be memory access. When checking along a scanline, this is not an issue, but rather the problems occur when you move vertically. Try to keep the entirety of an area that will all be checked at once in a single page of memory (approximately 4K). Either use smaller maps, or a tile based system. If you use a tile based solution, you should ideally only require a worst-case check against four tiles - the tiles should be bigger than the colliding object. When using a tile system, you can mark entire tiles as either "passable", "blocked" or "checkme". A polygonal scheme on top of this would allow further definition to the checkme, avoiding a potentially costly scan through the bitmap itself. Alternatives for this include a number of predefined collision patterns for tiles, rather than a terrain collision polygon.

But did it really take away from more deserving entries?

I do think that there is a lot of unfounded elitism being shown by all quarters in objecting to the nomination. I just played the game again for the first time since it initially made the viral rounds, and I do believe that it does indeed deserve recognition.

The game is not just a 'joke', the level of polish it shows is actually extremely high.

After clicking to start, your character is shown dropping into the level. This establishes the importance of the character, and as players are expecting a character, they then associate this character with the one they are to control.

The artwork used on the tileset is simple, but it is very well drawn, and creates a consistent feel. The simple addition of shadow creates an illusion of depth, and when combined with the player character, helps the player understand that this is a sidescrolling game, rather than say, a freescrolling game upon a map viewed from above.

They take a novel approach to a title screen. It is not displayed upon loading the game, but rather once you have entered the game. Notice how this polish mirrors the techniques often used in the film industry. Opening credits are also displayed at this stage, in a non-disruptive manner (they don't obscure the action, and do not stop the action).

One failing of the game is that it does not immediately tell you the controls, you are assumed to be familiar with the standard keyboard settings for games. Interestingly, however, trying WASD will teach you the throw axe command, and also direct you to the arrow keys. WASD tends to be the preserve of less casual gamers, and as such they are likely to take more notice of the axe action.

Music does not start until you begin moving. This hints at a sensible design concept - a paused-until-playing start to a level. The background music is again of a good quality, and helps to set the theme. The ominous nature alerts you to a struggle ahead, and the undertone of the strings hints at exploration.

As you move along the tunnel, tutorial information is given. The first message "there is a boss at the end of this tunnel" sets the scene well. Note how no information is given about the length of the tunnel, or what to expect from the tunnel itself. An easy to read font is used.

The second message "you can't hurt him with your weapons" will cause different reactions in the 'hardcore' and 'casual' players. If you immediately found the axe action, you will expect instead that you will have other uses for the axe. If you immediately used the cursor keys, however, this line hints that there is in fact a weapon, and players are likely to experiment to find one.

At this point, the tunnel turns upwards, indicating that some method of vertical travel is possible. This teaches you to jump, the most essential action in the whole game, and crucial to being able to complete it. Shortly after there is a drop downwards, which further reinforces the information from the start of the level (that there is gravity - you can fall, and falling does not do any damage). Although you may think this obvious from the start, many games over the years have had mechanics such that the entry to the level teaches you something which is patently false when actually playing the game.

At this point, progress forward along the tunnel is helped by the positioning of the third line of text, being just at the edge of the screen. Advancing to view this, you discover "To kill him you have to burn the rope above", which tells you that you will need to climb upwards somehow when facing the boss. At this point, the player is also introduced to a new mechanic - burning - which they do not have any more information about at this time.

The subsequent drop is higher than you can jump. This helps reinforce the sense of progression, and prevents the player getting stuck going back and forth over the same opening section. The next message is a simple "Have fun!", which establishes that this is an enjoyable, rather than challenging game. It helps reduce frustration when faced with the boss that is difficult to kill.

At the end of the tunnel, you come to a large room. The prior mention of "at the end of the tunnel" helps the player the realise that this room will likely contain the boss. This is instantly reinforced upon entering the room by the door behind shutting, a boss health meter appearing, and new music starting. The music is again fairly well polished, the base line giving a little tension, but the main theme being positive, empowering the player. At this point, we also see two new features, a window and the torches on the wall. The windows add further to the polish, fitting in with the tileset and breaking up the monotony of the rear wall. The torches are also visually fitting, and players are likely to be curious about them, given the earlier comment about 'burning'. However, they are also likely to assume that, given the window's apparent background status, the torches are background decoration.

The boss name itself helps - "grinning colossus". 'Grinning' is a positive action that typically we humans find a happy thing, however it is also associated with madmen. 'Colossus', on the other hand, is an imposing and fearful word.

On encountering the boss itself, it shoots at you through its eyes. The reactions upon your character being hit by these indicate to the player that being hit is bad. Interestingly, there is no actual game mechanics issue with being hit, however players are likely to want to avoid this. Similar reactions are in place when you hit the boss. The black colour of the boss is a traditionally fearful one, and the simple art style used not only continues to fit appropriately with the world, but also is a little comical, helping the player to enjoy the experience, rather than to feel that this is purely a dangerous challenge. When you throw an axe at the boss, an impact sound is played, indicating that it does hit the boss. The health bar (and its lack of response) helps reinforce that axes do nothing.

If you climb up the platforms in the middle, you are shown that the windows are background pieces only, and find the chandelier and associated rope. You discover that these are background pieces, and that you cannot stand on the chandelier. The need to deal with the boss is reinforced by the symmetry of the room, and the lack of any apparent escape route.

Using your jump atom of knowledge, you proceed up one of the segments at the side. It is difficult to avoid the torches, but this is possible. Complete exploration shows you that no other items exist in the arena, and so you are likely to then try hitting a torch (avoidance is likely if a player is an experienced gamer, since torches have in some games been items that harm you).

On hitting a torch, you gain a flame on a stick. This flame does not last forever - you have to reach the rope within a certain period of time. Jumping whilst holding the flame shows you that jumping will not put it out, making your possible routes to the rope suddenly open up (since you might know that you need to jump to reach it).

Hitting the rope causes the rope to burn, and the chandelier to fall. There is perhaps another aspect of parody here - the boss can be lured away from the centre, but when the chandelier falls, he moves back - forced defeatablity due to bad design The death animation again fits, they have smoke sprites in use, and sound effects. The boss's health bar falls, further reinforcing that you did it right.

The song at the end, and the ending video are again very well polished. The song does break the 4th wall, making this in some respects more of a meta-game. The line "but how are you going to spend the rest of this da-ay" is quite telling and appropriate, I felt. The song helps the player feel like they accomplished something, and it also works to 'wake' them from the experience.

This would have likely gone viral without all the polish. Plainer graphics, no axe action, no sound effects, an even simpler environmentally-defeated boss, and a far worse song at the end would have all worked just fine to make this viral.

What the nomination of this game shows is that to be nominated, games do not have to be long, or feature massive amounts of fancy content. What matters is quality gameplay (which this actually does have) and a good level of polish.

When I look at some the games it is against, I simply cannot understand the fuss that is being made over this nomination. The Graveyard is another game in the category, and that is simply about walking forward and sitting down (and if you pay, you get the chance at dying!). And some highly innovative games have still gone forward.

[This problem applies equally to OpenGL]

Whilst discussions of graphics APIs are great and all, could a mod please split this thread if possible? Draco came in here with a specific question, and it is unfair to them to have the thread derailed into an unrelated discussion, especially since the problem they are trying to deal with is API-agnostic. Once the thread is split (or not), I shall dive in with my own thoughts on this matter

Going back to the actual concern of the original poster:

Uhhh I'm specifically looking for help using a surface and cutting that surface up into textures.

What I believe they are trying to do is implement this section of the tutorial:

What we need is a way to break up a (potentially large) bitmap into smaller images to be stored in textures. The easiest way to do this is to load the entire bitmap into a Direct3D surface (which have no size restrictions) and then use CopyRects to copy surface sub-images into textures.

The demo program uses D3DFMT_A1R5G5B5, a 16-bit surface format where five bits are reserved for each colour and one bit is reserved for alpha transparency. Other suitable surface formats are D3DFMT_A8R8G8B8 and D3DFMT_A4R4G4B4. (See CreateSurfaceFromFilein the demo.

You need an alpha component in your surface format for transparency, and an RGB component for the colours to display correctly. The exception to this rule is D3DFMT_A8R3G3B2, which (in my experience) has insufficient RGB values to produce a good range of colours and often results in an incomprehensible grey image.

The same surface format is used for the textures. (You will not be able to copy data between textures and surface otherwise.)

In most video cards, the width and height of a texture must be a power of two. A 20x40 image will be stored in a 32x64 texture. This extra area within our texture must be set to a transparent colour or random colours may surround your sprites.

Newer video cards let you create textures that are not limited to powers of two.

To clear the texture we need to create a blank surface and then copy its content over to the texture. Can't we clear the texture directly, you ask? We can but textures placed in the D3DPOOL_DEFAULT pool cannot be locked for clearing [1g]. Placing our textures in D3DPOOL_MANAGED memory will allow us to lock the texture but the copy method works for both cases so it is more flexible. See CreateTextureFromSurface in the demo.

Finally, we can copy the bitmap image over to the texture.

This section specifically addresses the problem of texture sizes. Graphics hardware has traditionally had a maximum size and dimension of textures supported. This problem applies equally to OpenGL, hence why the API discussions really belong elsewhere (Although for OpenGL, the solution would be quite different).

Looking into IDirect3DDevice8::CopyRects, it seems that Draco's most likely problem is that I think this function no longer exists on the IDirect3DDevice9 interface. One quick search later, and the appropriate alternatives (in theory) are found!

Where exactly are you getting stuck?

An object might also have a list of sprites, or might change the visual appearance during its lifetime.

I'm actually thinking that perhaps it is more important that an object might not be a sprite - there are many great uses for invisible objects in a game world.

This hence automatically forces a has-a relationship, rather than an is-a (and all you need do is have either null checks, or a stub display class)

Case 1) If either class might change in the future I'll express their relationship using whatever software structure best models their conceptual relationship to minimise the possibility of some future change breaking my implementation.

Three common practices mitigates this concern somewhat. Firstly, when working according to interface specifications (which you should), it is a good idea to define the scope of any class such that major changes to an interface should not be needed, and any internal changes should not be exposed to the outside world. Secondly, although this does not directly fix the problem, unit testing helps to quickly identify exactly where the fault lies, allowing even major revisions to be quickly done, checked, and corrected for. Finally, there is a very old adage that is hard to work to, but a very good idea - design for the present. It is easier to work in new features to a well-built product, than it is to try and both think of every possible usage and to keep the implementation solid.

If there are any problems, remember that the facade or proxy design patterns could be used to easily fix the problem whilst following good design practices.

Case 2) If neither class will change in the future I'll express their relationship using whatever software structure gives me the best tradeoff between implementation time and runtime resource use.

Of course, however remember that optimisation should be a last-stage process. Depending upon your compiler, however, there could well be little difference (remember that virtual function calls have greater overheads than non-virtual).

I'm not really sure if you need this optimization in modern CPUs actually

Checking Intel's docs, they do have a nice Reciprocal of Square Root operation available, which was added in the first version of SSE.

The alternative to these opcodes would be proper calculation by hand. This would be very slow if done by any other technique. The biggest magic in the Quake fast inverse sqrt seems to be a really good starting number, such that it does not need to iterate to get within the required error range.

A model-viewer-controller setup is probably the best way to go. It gets more complex initially, but allows greater freedom of editing in the end. Take a look at this for how one group of professionals implemented it. I felt it was too complex the first time I saw it, but the more I read, the more it made a lot of sense.

Other advantages of an MVC system include easier testing, and far easier porting to different platforms.

As for the containment/inheritance discussion on it's own, I found this a useful discussion on the subject. In general, look to use containment. An important thing to look out for is when something actually has a IS-NOT-A relationship, which was something I hadn't considered before reading that article.

I wouldn't use volume. That ties you to recorded music, and I prefer the idea of being able to distribute programs as scores. That would also allow your program to be performed, and by not specifying volume, you allow more artistic interpretation.

My current thoughts are to use groups of eight notes as the word size (CS term, rather than MS programming term), then simply using a fixed instruction/data size of 1 word, making a complete opcode (instruction + data) 3 words long. Instructions that need less data words would simply ignore the extra words. This keeps it simple to interpret, allows fun tricks (like reusing sections of code in different ways), and (importantly) offers the programmer/musician space to be artful.

In implementing a VM, I have came to the conclusion that registers are best avoided, and instead to work with a memory model alone. I believe this is how the Java VM does it (but it has been a while since I read the specification), using only a program counter and some flags.

In my experience, rather than using the idea of displays, a more generalised streams approach actually offers a lot more flexibility. You simply bind different input or output devices to the stream number/address (you could make these memory mapped, but that means you have to consider two different types of memory location, and from experience this quickly becomes a pain). This would even allow extremely strange things, like binding a stream to write to real memory, and another to then interpret words sent to it as API function calls with the data in the previous stream being used. Using this system also allows different streams to be set up for ascii output, and musical output.

To go extremely technical, a very clever thing to do would be to have values both being valid computational numbers, and being valid notes. By storing them in this fashion, you become able to process music as well as numbers, with the conversion being automatically being taken care of. The important thing here is to ensure that the same basic properties of working with numbers also applies to working with the music:

• When adding two numeric values, the sum is the same as when adding two notes, and vice versa
  
• Subtraction of notes should reverse addition of notes
  
• ...Similarly for multiply and divide
  
• ...And left shift and right shift
  
• If many musical representations of the same number exist, all operations should map according to that note set, hence maintaining all axioms properly.

This would be fairly simple to do using a C++ class for representing the data. Sound output can be easily cheated by using SDL_Mixer or somesuch

Even though processing a midi file into an instruction set wouldn't require much theory, just assign a different instruction to each pitch, and let instructions be executed in parallel when there's a chord (could make it really weird like that)

Or go the piet route and have the change in pitch between notes represent the instruction to be executed

Or the size of the chord could be the instruction, allowing some musical arrangement of the chords

Rest = Nop

That's a good start!

A really interesting touch I would love would be to have it inherently concurrent - each instrument's score is a different thread. Matters of locking could be avoided by simply assigning varying priority to differing sections of the orchestra/band (which ok, makes it less concurrent, but simple is good )

There are two different types of symbol to consider - opcodes themselves, and the data to go with them. There tends to only be a few opcodes, but in a RISC system they would repeat regularly unless means were found to allow them to each differ. Data typically needs to vary over a large range.

As such, I think it would be better to consider groups of notes, rather than individual notes.

From my work with the single instruction instruction set, I know that a registerless VM can work quite well, and means you have fewer opcode conditions to consider. I would probably consider using such a setup, and it feels appropriate for the problem - dancing along the memory. A Von Neumann architecture would also be a must, self-modifying music would amuse me

I wish I was more musically inclined - I feel this problem would be better addressed by working with the art first, and then fudging the figures used to ensure that whatever is written in the notes could sound good. What we need are repeatable structures of notes that can vary in their internal make-up (for the opcodes), and a sensible representation of literals that will also result in good sounds (this could also be based at least somewhat on patterns, rather that required positions).

If we can get the music figured out, I would be interested in throwing together a VM for this, actually I can certainly do the core VM easily enough, and perhaps musical output and graphics. Not being a musician, getting live midi programming to work would be difficult, but tempting in the long run.