Announcement

**Quake Jesus** · 07-14-2011, 01:23 AM

Well it seems that there is a flag SURF_PLANEBACK that tells it if the plane normal is pointing down so I can tell if it is a ceiling, but now I am obsessed with how to walk the BSP tree. And now that I am obsessed, I am going to figure it out now. Not that I really have much use for it other than for making the AI do whacky things and walk around without falling into the lava every 5 minutes.

**Quake Jesus** · 07-14-2011, 04:20 AM

Well not much activity here so I am just going to continue with my investigations, maybe this can help someone else out.

So I was obsessed with the BSP tree, but then I became even more obsessed with planes and the surfaces. So I messed around in there, and eventually lo and behold, I pulled out all the polygons and found the potential floors! But it's a convoluted tale that begins many years ago when I was a wee tyke, first learning to grok this crap to my own unfortunate demise.

I recalled the first 3d engine I wrote, on my 3dfx voodoo card, that could read Quake maps and display them. But there was a major problem see. The original voodoo could not draw to a window, so debugging my horrendously bad 3d engine (was just a really bad quake map viewer in all honesty) I had to dump everything to files to try to figure out why it crashed AGAIN for the millionth time. So flash forward now to the present, with me merrily debugging Quake in a window, and thinking you know at least some things have changed for the better. Ahh the memories.

Ok so getting back to these surfaces I had to crack the mystery of where the hell the polygon faces were stored. In the code there is a gpoly_t structure, which looks tempting, but there is nothing in it! I see later on, it is used, but at this point I am just calling a C function in QuakeC in the Worldspawn to poke around with this stuff and figure out what is in it. Then I remembered the edges, and I flashed back to that horrendous 3d map viewer program and the hideious 3dfx voodoo no-window-rendering and chuckled.

So I came up with this crappy function

Code:

void PF_BuildNavMesh_0()
{
    model_t * m = sv.worldmodel;
    plane_t * p;
    glpoly_t * gp;
    int i,j,k;

    // walk the surfaces if flags & SURF_PLANEBACK is in surfaces then I guess it is a ceiling?
    for(i = 0; i < m->numsurfaces; i++)
    {
        p = m->surfaces[i].plane;
        // gp = m->polys; // this is useless there is nothing in them

        // is this the floor or ceiling?
        //if(m->surfaces[i].flags & SURF_PLANEBACK) continue;

        // I guess this is the floor let's see
        //if(p->normal[0] == 0.0 && p->normal[1] == 0.0 && p->normal[2] == 1.0)
        {

            // I guess I have to use the edges to get the vertexes
            // If I recall the edges are the winding of the polygons in the soups, been a long time since I messed with quake stuff.
            // this is from gl_warp

            int			numverts;

            int			lindex;
            float		*vec;


            for (j=0 ; j < m->surfaces[i].numedges; j++)
            {
                // start with this surface edge list and then get the vertices
                lindex = m->surfedges[m->surfaces[i].firstedge + j];

                if (lindex > 0)
                    vec = m->vertexes[m->edges[lindex].v[0]].position;
                else
                    vec = m->vertexes[m->edges[-lindex].v[1]].position;

                printf("%f %f %f\n",(*vec,*(vec+1),*(vec+2)));
                numverts++;
            }

            num_floors++;
        }


    }

}

Well wallah I had found the friggin polygons and the bloody vertexes. Hoo hah. So now I can find all polygons that should potentially be navigatable on (don't have to worry about flyers now) but now, I have to figure out if it's a good polygon or a bad polygon, because bad polygons are lava and bots should not jump in the lava ever.

**Quake Jesus** · 07-15-2011, 03:14 AM

Well I guess not too many coders around these days, they are all hopefully working and busy I hope.

So I thought I'd come back and check if anyone had posted but

So here is some new stuff I grok'd while looking for the floor. I am looking for the floors I tell you. Anyone see the floors?

Ok enough silliness. So I made my brain actually work for once, and actually got off my lazy butt and did some programming. I used to like programming once, and C code is something I like. I had done C++ and Java but it was kind of lame, I really didn't like programming. I just like hacking video games and making them do stuff. So I read alot of books on this stuff but today the industry is very different, and I just don't really care much for it. But Quake is open source see, and it gave me alot of happiness blowing monsters up. And you know Valve and Call of Duty, and many engines today still have quake code in them. There is infinite potential in the source code, source code is useless without art and map and stuff to make a world that is fun to play in see. Code is just a means to an end.

Ok so here is what I whipped up, if anyone out there finds it useful. I still am not ready to make a navmesh, we got a long way to go, but at least now we can find potential floors that can be walked on. We'll have to walk the BSP later I think, to figure stuff out like if it is Lava or Slime, but it doesn't look very hard to do it as there are functions in Quake that will do it for us. But hey, programming always looks easy until you realize you didn' tthink about something beforehand hehe.

Code:

// I don't remember if Quake uses polygons other than triangles so it is just arbitrary for now
#define MAX_FLOOR_VERTS 10

// structure to hold potential floor polygons for now
typedef struct floor_s
{
    plane_t * pplane;
    vec3_t  verts[MAX_FLOOR_VERTS];
    int numverts;
    struct floor_s * prev, * next; // link list pointers
}
floor_t;

floor_t * pfloors;
int num_floors;


// ok see even if something appears to be floor it might not be
// imagine a square room and in the center is a giant crate that is too high to jump on. Well the polygons on top of that crate
// would point up, and this code would think it was a floor. But there is no way to navigate to it because it is too high to jump too,
// and should be culled out later on. But this would be done when figuring out the graph for the navmesh anyhow, I think. I don't know,
// I know the theory but never did it before. But what would be done, is to compute convex hulls around those polygons and group them into
// convex polygons, and then walk the edges of those convex hulls and determine which are connected. This needs to be done because the world
// is made of triangles, and there are alot of them, and it would make the AI dodgy. All the AI would need to know is a convex polygon,
// That convex polygon is just a hull around a bunch of triangles
// that are the actual polygons in the world. I think anyhow, I'll find out. I always wanted to program this kind of thing.
void PF_BuildNavMesh_0()
{
    model_t * m = sv.worldmodel;
    plane_t * p;
    glpoly_t * gp;
    int i,j,k;
    floor_t     *pf, * prev = NULL, *hd = NULL;


    // walk the surfaces if flags & SURF_PLANEBACK is in surfaces then I guess it is a ceiling?
    for(i = 0; i < m->numsurfaces; i++)
    {
        p = m->surfaces[i].plane;

        // is this the floor or ceiling?

        // I guess this is the floor let's see
        if(p->normal[0] == 0.0 && p->normal[1] == 0.0 && p->normal[2] == 1.0)
            if(!(m->surfaces[i].flags & SURF_PLANEBACK))
            {
                int			numverts;
                int			lindex;
                float		*vec;


                pf = Z_Malloc(sizeof(floor_t));
                pf->pplane = p;
                pf->numverts = 0;
                pf->prev = NULL; // z-malloc does zero memory but better safe than sorry
                pf->next = NULL;
                if(hd == NULL)
                {
                    hd = pf;
                }

                for (j=0,k=0; j < m->surfaces[i].numedges; j++,k++)
                {
                    // start with this surface edge list and then get the vertices
                    lindex = m->surfedges[m->surfaces[i].firstedge + j];

                    if (lindex > 0)
                        vec = m->vertexes[m->edges[lindex].v[0]].position;
                    else
                        vec = m->vertexes[m->edges[-lindex].v[1]].position;

                    //printf("%f %f %f\n",vec[0],vec[1],vec[2]);
                    VectorCopy(vec,pf->verts[k]);
                    pf->numverts++;
                }


                // link the list
                pf->prev = prev;
                if(prev)
                {
                    prev->next = pf;
                }
                prev = pf;

                num_floors++; // well just do this for now
            }
    }
    pfloors = hd;

    // just see if this stuff was done correctly
    while(hd)
    {
        int i;

        for(i = 0; i < hd->numverts; i++)
        {
            printf("vertex: %f %f %f\n", hd->verts[i][0], hd->verts[i][1], hd->verts[i][2] );
        }
        hd = hd->next;
    }
}

**Quake Jesus** · 07-15-2011, 04:18 AM

Ahah! Look at this cool stuff

recastnavigation - Navigation-mesh Construction Toolset for Games - Google Project Hosting

Now that looks bitchin'. Imagine quake bots running around with the brains of MIT! I am so going to use that even if it is C++ it won't be impossible to make it work in Quake. And seeing I am lazy, and no way can I do better than some MIT dudes, I am going to hook that code into there instead hehe! Then anyone who wants to play around will have MIT brains to path their AI in quake! MUHAHA!

Be back later when I figure out how to use that stuff

**Quake Jesus** · 07-16-2011, 12:00 PM

Well I figured it out, it's not working perfect right now tho. While I was at it, I used what I had found to put waypoints automatically on a map. That's not working perfectly either, but I think I will have it working in a few days. But the code is just way to much to post, so I have plans sometimes to put this code up for other modders who would like path navigation for their mods. I have big plans to do what I think needs to be done for modders to use the Quake engines in the 21st century and have alot of flexibility with it. Well talk is cheap so I won't go into that more, but I'll be back sometime with a hopefully robust navigation system for modders to use to make more interesting AI.

See yah later!

**R00k** · 07-16-2011, 12:22 PM

Very interesting stuff! Thanks for the link. You might find more active Quake coders over at Inside3D - Quake Modding - Because you can't be outside 3d!...

**Quake Jesus** · 07-16-2011, 02:55 PM

Thanks, I see you have done lots of work in the engine, as I doubt there is another RooK around. I hadn't been in the quake community in many years and was glad to see it still is going.

My goal is to provide this code as plugins so anybody can put it into their favorite build. It might be tricky in Dark Places because he modified the quakec code quite a bit. Otherwise it should be easy to hook in to any build, I think...

I probably outta change my name, I was listening to Jonny Cash's version of Personal Jesus ‪Johnny cash - Personal jesus‬&rlm; - YouTube when I was registering lol. I want my own personal Quake Jesus to save me from the dull games they are making these days. Everything is modern warfare now, and boring.

See you later I got to sleep a bit now.

**Quake Jesus** · 07-18-2011, 12:38 PM

Here's a little video showing off some of the auto waypoint and A* path functions I have done, there are still issues with the steering because I am using Quake's move functions. I am still working on waypoints so mappers can add them manually if they want because there are some dodgy issues with platforms and func_trains.

Right now they all just follow me around the map, and they won't attack because I made them all peace loving hippies.

[ame=http://www.youtube.com/watch?v=IrLmWWXWeoc]‪Showing A* path calculations in Quake using automatic waypoints #1‬&rlm; - YouTube[/ame]

**Quake Jesus** · 07-22-2011, 08:34 AM

Hey guys,

The waypoint path finding is working awesome now. I am still working on the Navigation Mesh code and new AI navigation code. Now the monsters can find you anywhere on the map! I decided to ditch recast navigation because it wasn't very difficult to find the walkable areas and it required triangulating all the polygons in the map as Quake uses polygons other than triangles in the BSP.

But now I am replacing QuakeC with Lua. It is a much better scripting language and would allow editing scripts in Quake in a sandbox. You will see it is a much better idea and my goal is to modernize the quake engine for people to use it to develop games and mods. Quake has tons of tools and knowledge so why use some crappy code when you can use a commercially proven engine to make your game?

**Zop** · 07-25-2011, 07:52 PM

Adding a lua interpreter would be interesting, since it could open the doors to modding quake for more people, but it'd put me out of business as a quakeC programmer!

Announcement

Quake BSP/brush question

Quake BSP/brush question

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment