PDA

View Full Version : 48HP3: Zombie Neighbourhood



CiNiMoDZA
19-03-2011, 11:34 AM
If, when you read the title of this thread you assumed it was going to be another
top-down zombie shooter...you were right!

Concept: So, for you to understand where we coming from here, we need to go back a while. (A while) So my room-mate(who is a red-head) and myself were playing a game of L4D when he randomly realized that there were no ginger zombies! Frustrated, he searched for any game that contained ginger zombies. Well, we have found them, all of them.

You are trapped in your neighbourhood with no rescue party in sight. You are safe to wonder the streets during the day as read-headed zombies are very sensitive to the sun(one explanation why they don't feature in most zombie survival games already). Use this time to find resources. Food, weapons, building materials, all these are going to be critical if you want to survive. At night, find shelter and pray that you have secured your home base sufficiently. Its going to be a long night for you....

Gameplay: Top-down zombie shooter with a survival element to it.

Controls: Copy and paste from any other zombie shooter you've ever played!!

Challenge: Do something weird

Restriction: Use our voices for sounds

Technical Stuff: We'll be using XNA 4.0 and making a PC game. If anyone knows where we can find a code sample that does pathing(kind of like GM's mp_potential_step) that would be awesome, as this is our biggest worry at the moment! Everything we us make this game will be created in a separate library and also shared so any criticism on there will be great

Downloads: Erratum (http://www.mediafire.com/?xjlc5o7ah6008ri) The random name our random name generator generated for our library! Still very much beta!!!

**Note: For anyone wanting live updates on the project, the Twitter account Dominic_Nologo will be tweeting as we go!**

edg3
19-03-2011, 12:45 PM
look up a*, its not difficult to implement, or if you cant understand it read up on breadth first search (graph theory) which is essentially the same thing.

The network prediction sample may have some path finding.

CiNiMoDZA
19-03-2011, 12:48 PM
Awesome...I was looking into that a* algorithm thing, but we going to get the basics down first and then do that!

Fengol
19-03-2011, 01:37 PM
Do you mean red-haired zombies?

http://i139.photobucket.com/albums/q312/Fengol/GingerKids20.jpg

CiNiMoDZA
19-03-2011, 03:41 PM
Ok, 4 hours in. We (myself and Krummelz) have been hard at work :P In the first post you can find a link to the library we are creating as we are going along.

I have been focusing on getting those core things done while Krummelz has been hacking away in Photoshop to get us some pretty little images!! Will upload a SUPER basic version with just movement and what the game is going to look like after the break!!

edg3
20-03-2011, 09:44 AM
Read this first, if it gives you a decent idea follow it rather (http://www.policyalmanac.org/games/aStarTutorial.htm)

Ok, here is essentially what you should do:

Im going to use a structure that doesnt require an actual graph (so if you have a 100x100 level you wont have an insane number of checks to do. Also, for this to work, we dont include the border of your level when we loop through (so from row 2 to num rows -1, and column 2 till num cols -1).

Then we will use the following powers of 2 for the different directions that are open:
[8] [1] [2]
[7] * [3]
[6] [5] [4]

This allows us for the path finding to say "if (currentblockvalue & 2^8)" to check if we can move up diagonally, and so on.

When you create your level (which I'm assuming is some kind of grid) Pseudocode:


List<int[]> Graph = new List<int[]>();

void MakeGraph(yourlevelstructure)
{
for (row in yourlevelstructure)
{
Graph.add(new int[length(row)];
//check each direction
for (position in row)
{
int am = 0;
if (up on yourlevelstructure is pathable from current position)
{
am += 2^1;
}
if (upright on yourlevelstructure is pathable from current position)
{
am += 2^2;
}
if (right on your level structure is pathable from current position)
{
am += 2^3;
}
//all the way up to 2^8 for upleft, if you have 8 directions you can move
Graph[Graph.length-1][position] = am;
}
}
}

So this will give you a list of values for where you can move (note: if you only move in 4 directions like pokemon, this becomes simpler)

The next step you can do in 2 ways, the proper way, and a hacky way, this is the (semi) proper way, as it does a breadth first search (the reason this works with lists is you dont want your AI to run this every frame, and you dont want to run it on every enemy at the same time, otherwise it will be very slow)

The path finding


List<Vector2> ShortestPath (int x, int y, int start_x, int start_y, int max_depth) //note X,Y are not in world co-ords, they are in graph co-ords
//max depth is the furthest path this algorithm is allowed to check.
{
List<List<Vector2>> CurrentPaths = new List<List<int>>(), newpaths;
directions_avail = Graph[start_x,start_y];

for (dir in directions(directions_avail)) //this will actually be for (int i = 0; i < len direction; i++)
//so that you can us l.add(i), whish is the actual direction
{
List<int> l = new List<int>();
l.add(dir);
CurrentPaths.add(l);
}

num_options = 1;
while (num_options > 0 && max_depth > 0)
{
num_options = 0;
for (Path in CurrentPaths)
{
if (move(Path)) //if we follow the path, and end at the end, this is the end of the path for us
{
return Path;
}
//otherwise find all new paths and add it to the list
}
newpaths = new List<List<int>>()
for (Path in currentpaths)
{
newplace = move_to(path, start_x, start_y);
directions_avail = Graph[newplace.x,newplace.y];

for (dir in directions(directions_avail)) //this will actually be for (int i = 0; i < len direction; i++)
//so that you can us l.add(i), whish is the actual direction
{
List<int> l = new List<int>();
for (item in path)
{
l.add(item);
}
l.add(dir);
NewPaths.add(l);
}
}
CurrentPaths = NewPaths;
max_depth -= 1
}

return new List<Vector2>();
}
int[] directions(direc_avai)
{
int[] arr = new int[8];
if (direc_avail & 2 == 2)
{
arr[1] = 1;
}
if (direc_avail & 4 == 4)
{
arr[2] = 1;
}
if (direc_avail & 8 == 8)
{
arr[3] = 1;
}
//and so on, also I may be thinking wrong with the (direc_avail & 8 == 8)

return arr;
}
bool move(List<Vector2> Path, start_x, start_y, end_x, end_y)
{
for (item in path)
{
if (item == 1) //up
{
start_y -= 1;
}
else if (item == 2) //upright
{
start_x += 1;
start_y -= 1;
}
else if () //etc
{

}

if (start_x == end_x, start_y == end_y)
{
return true;
}
}
return false;
}
Vector2 move_to(List<Vector2> Path, start_x, start_y)
{
Vector2 pos = new Vector2(start_x, start_y);
for (item in path)
{
if (item == 1) //up
{
pos.y -= 1;
}
else if (item == 2) //upright
{
pos.x += 1;
pos.y -= 1;
}
else if () //etc
{

}
}
return pos;
}


I hope I didnt miss anything, and I would have to write this code out properly to test it, but it should have minimal processing overhead if you only do checks up till depth 5, you wont continuously loop until you find the player, you will only check till max_depth (so length of 5 if depth 5). also, it returns a blank path if it doesnt find the end (meaning the ai doesnt have a purposeful target).

Hope it helps

CiNiMoDZA
20-03-2011, 11:58 AM
Ok, that makes sense except for the youLevelStructure variable?? How do I get that?? I have a pretty big level (like 6000x6000), do I have to make an array with 36000,000 points and constantly have that stored?? That doesnt sound very efficient or am I understanding wrong??

edg3
20-03-2011, 12:14 PM
6000 by 6000 pixels? Split it into 30 by 30 blocks for ai pathfinding. (200x200 then).

Your level structure is what is walkable and what isnt. If you use an image for pathing it gets more complicated, but we can always simplify it to a datastructure that we can use.

So what is your level? How do you determine where you can walk? How are you storing these in c#?