All the flexibility with little complication?

I'm making a game that would best be described as a side scroller. I'm in the planning stage of this game and I'm looking for some ideas.

I have three main elements so far...
The player:
- Moves around the level, jump up, drop down, move left and move right.
- Attacks enemies adjacent (left or right)

The Enemies:
(Many different types but all have these fundimentals)
- Moves in any combo of these: left, right, jump up, jump down.
- Some may attack with bullets (or fire, havn't decided ;) )

The Level:
- any given square can allows the player (and enemies) to move freely through left and right, it can be stood on top of and wolked through (left and right). If the player/enemy is below it they can jump up through them and land ontop of or inside one... I hope this describes them well enough.
- some squares can not be jumped or moved through, only walked on top of.

Thats about it for the description, any unclearities ask.

Now if you're still reading heres my question:
I'm looking for a good way to know where the player/enemy can or cannot go. Im thinking that I assume the current position is a valid place for it to be, then move it with its x speed and y speed to get a new position and it thats not the same square then check to see if they can and if not then revert to the old position??? Sound good you guys?

It sounds good to me, but if you can think of anything I can't or forsee some problem I'd really appreciate the insight.

Thanks (just for reading this),

NOMAD

Well if all of your tiles are going to be the same size, you could just have a text file define the different kind of blocks, here's an example:

00000000000000
11100001111001
00001100000000
22200031444444
22211001444444
11111111111111

0 - Plain air, can be passed through in any direction
1 - Solid, can be passed through by jumping up, but not left right or down.
2 - Ice, Completly solid, can not be passed through, but slick on top.
3 - Spring, can not be passed through in any direction, but on top is a jump pad.
4 - Water, can be passed through, but always floats you to the top. Can not swim down.

This is just to give you a little idea of how your system may work. Just hard code all of these materials into your game engine or whatever, good luck.

-Dylan

Thanks D Viddy,
good call on the text file!

I'm on my way!

NOMAD

That's all well and good for terrain but how about the creatures on the board. How are you going to detect their presence so that they don't "phase" through each other?

IntersectRect

How about a nodal grid in which each node represents the terrain being unblocked or blocked? That way you can check to see if the new position will be blocked by checking the node (or nodes) that the creature will occupy if it moves to that spot.

If you use IntersectRect (unless if I am mistaken) wouldn't you have to compare the rectangle to all rectangles on the board?

Thanks for the responce DarkWraith.

Sorry if this is wrong, but how is that different from what I suggested, other than using the word 'nodal'.

You are not mistaken you would have to use it on all rectangles on the board, but only players and enemies would be checked against. Im planning on using the system I mentioned in my first post for checking the background.

NOMAD

With the nodal system, you only have to check only a few nodes while the rectangle system, you have to check all rectangles.

I think I have some code laying around for this type of implementation if you want.

no need I already have plans to implement your nodal grid for my background tiles, as for the enemies I see no better way than to use IntersectRect on all of them compared to the players.

NOMAD

If all of your enemies are ground based, you can use the same nodal system for collision detection. So essentially, you can have an algorithm of O(n) (with nodal) instead of O(n!) (with rectangle.)

Now there's fast for you! :)

hmm n! ehhh? If n is the number of enemies, as im assuming it is. I was planning on having the non-ground enemies able to phase through all other types on enemies. so if n is ground enemies. But the ground enemies could implement a nodal grid system except the grid system would take longer to check then a single api call.

Plus I cannot for see a very large number of ground enemies where n and n! difference is substancial to make up for the grid checking. Unless of coarse your checking algorithm is better than mine. How do you do it?

NOMAD

Why couldn't you just have one occupant per tile, and whenever a creature wants to occupy a tile, it has to check the next tile to see if it's availiable. So each tile will have a simple boolean value to represent if it is occupied or not. That way, for each movement of a creature, only one if statement has to be used.

-Dylan

good plan, but when I go to move them I will have to make code to know when to move a enemy into a new tile, this code will be as lengthy as the checking method we stated above.

I'll keep that plan in mind in case I run into a problem with the first way, I love the alternate ideas!

Thanks!

NOMAD

On second thought, maybe I mispoke. I think the rectangle way is O(n(n-1)). Furthermore, it depends on how you are having them collide. If you are just checking for final position in which the final position tells you if movement is possible (which mine does,) then you will achieve a O(n). If, however, you are comparing movement to all other positions of all other entities, then you will have O(n(n-1)) (your rectangle system.)

So, let n = number of entities.

So in order to check the movement of 5 enemies:

O(5) = 5*k
O(n(n-1)) = 20*K

where k and K are undetermined constants dependent on implementation.

Now what will happen if we are to do this with 100 entities? Well, then we will need a sorting algorithm to try to bring the rectangle implementation to something realistic, and that requires more resources and more complexity.

This algorithm only counts entities that require collision.

I'll post the code once I find it.

Your method require the grid data type to look up the possibility of the move by checking data stored in a node correct? how many nodes are we talking about?

Your system sounds complicated, where the rectangular system's K will be near 1 but depending on the amount of code needed to generate and execute the nodal system, your k could more than compensate for the difference in O values.

I would be interested in seeing your code sample, thanks for the help!

NOMAD

I reread your post, i dont think K and k are the constants that the complexitiy would be effecting, but my worry still stands...

NOMAD

It requires the creation of a 2 dimensional array of nodes spaced at a certain (kx , ky ) that represents the fact of the landscape being blocked or not. This is not too hard.

Finding the creature's position is not too hard ( C: (floor(x / kx), floor(y / ky)) ).

Finally, checking and updating the position so that the terrain is blocks is like throwing a few switches, negligible.

This amount of added cost is more than compensated once you have ten creatures on the board:

O(n) = O(10) = 10 * k
O(n(n-1)) = O(10*9) = 90 * k

The second algorithm's cost grows quicker than the first.

In terms of complexity, think of the nodal grid as a chess board. Each node can be occupied by only one creature. Movement is basically the same. To represent blocked terrain, mark a few squares as always occupied and have the pieces move. Easy.

Still looking for my files.

Good idea, it could also mean that with a little extra and some smaller grid nodes you could make it a 2d polygonal intersection algorithm... good call DarkWraith, good call.

If you find that sample post it, if not I think I have a pretty good idea of what you're saying. I may post questions about your method in this thread.

Thanks again for the great idea!

NOMAD

I just thought of something... :D

I figured out how to keep the nodal algorithm fast even with lots of entites in the world (over 1000, much like Empire Earth.)

Its experimental, but try to only do collision on the ones that are moving (velocity != 0.)

For example, let n = 1000 = number of total entities
and m = 100 = number of moving entities

Using the nodal approach, you only have to work with the moving entites so nodal will be 100*k instead of 1000*k. (Needless to say, rectangle dies in this amount. (100*999 = 99900))

I thought that it might be useful to point this out depending on how many entities you are going to have at any one time. :)

Thats a good point, unfortunatly this particular game Im planning everything moves all the time. I'll definatly keep that in mind if I do a RTS or something like Empire Earth.

NOMAD

Do you mean that everything will have the capability of moving each cycle or do you mean that everything is moving each cycle?

Just a note on the previous numbers:

The numbers are based on the collision being on one node. If you are going to create multi-nodal creatures, the algorithm will be O(n) = n * p * k, where p is the average number of nodes that the entity will occupy.

I can't find the file on my desktop (probably on my laptop) so it might take awhile. :(

Capability, but nothing will have a velocity on 0. But the entities will be on a timer (GetTickCount) that tells them when to move next. So only these enemies will be ran through the algorithm.

If Id he multi-nodal collision it would still be faster (even a little) than the IntersectRect, and I've had over 100 (more than Id need) with the IntersectRect method and stil maintained a playable fps.

NOMAD

D.Viddy, that's what the collision aspect of the node is, a boolean value representing if a node is blocked or not.

I use the word "node" instead of boolean value because you can build upon the node to include landscape characteristics, pathing / waypoints, and all sorts of other things. :)

DarkWraith: Thank you for clearing that up for me.

-Dylan

Viddy, is your text file per chance a Jump'n'Bump level?

HaHa, nice call CornedBee. It isn't exactly a jump n' bump level, I just used my memory. But yes, that is where I got the idea for NOMADMAN. Nice observation. :D

-Dylan

That game rocks hard...

There was a time when that was the only game I would play. :D

-Dylan

We installed it on the classroom computer and spent all breaks playing it...

Now that would be a good time passer. Also try ICYTOWER.

-Dylan