path: root/src/jake2/server/SV_WORLD.java

/*
Copyright (C) 1997-2001 Id Software, Inc.

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  

See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

*/

// Created on 07.01.2000 by RST.
// $Id: SV_WORLD.java,v 1.1 2004-07-07 19:59:50 hzi Exp $

package jake2.server;

import jake2.game.edict_t;
import jake2.game.trace_t;

import jake2.*;
import jake2.client.*;
import jake2.game.*;
import jake2.qcommon.*;
import jake2.render.*;
import jake2.util.Vargs;

public class SV_WORLD extends SV_CCMDS {

	// world.c -- world query functions

	//
	///*
	//===============================================================================
	//
	//ENTITY AREA CHECKING
	//
	//FIXME: this use of "area" is different from the bsp file use
	//===============================================================================
	//*/

	//// (type *)STRUCT_FROM_LINK(link_t *link, type, member)
	//// ent = STRUCT_FROM_LINK(link,entity_t,order)

	//// FIXME: remove this mess!
	//#define	STRUCT_FROM_LINK(l,t,m) ((t *)((byte *)l - (int)&(((t *)0).m)))
	//
	//#define	EDICT_FROM_AREA(l) STRUCT_FROM_LINK(l,edict_t,area)

	//

	public static void initNodes() {
		for (int n = 0; n < AREA_NODES; n++)
			sv_areanodes[n] = new areanode_t();
	}

	public static areanode_t sv_areanodes[] = new areanode_t[AREA_NODES];

	static {
		initNodes();
	}
	public static int sv_numareanodes;

	public static float area_mins[], area_maxs[];
	public static edict_t area_list[];
	public static int area_count, area_maxcount;
	public static int area_type;

	// ClearLink is used for new headnodes
	public static void ClearLink(link_t l) {
		l.prev = l.next = l;
	}

	public static void RemoveLink(link_t l) {
		l.next.prev = l.prev;
		l.prev.next = l.next;
	}

	public static void InsertLinkBefore(link_t l, link_t before) {
		l.next = before;
		l.prev = before.prev;
		l.prev.next = l;
		l.next.prev = l;
	}

	/*
	===============
	SV_CreateAreaNode
	
	Builds a uniformly subdivided tree for the given world size
	===============
	*/
	public static areanode_t SV_CreateAreaNode(int depth, float[] mins, float[] maxs) {
		areanode_t anode;
		float[] size = { 0, 0, 0 };
		float[] mins1 = { 0, 0, 0 }, maxs1 = { 0, 0, 0 }, mins2 = { 0, 0, 0 }, maxs2 = { 0, 0, 0 };

		Com.Printf("SV_CreateAreaNode " + depth + "\n");
		anode = sv_areanodes[sv_numareanodes];
		
		// just for debugging (rst)
		VectorCopy(mins, anode.mins_rst);
		VectorCopy(maxs, anode.maxs_rst);
		
		sv_numareanodes++;

		ClearLink(anode.trigger_edicts);
		ClearLink(anode.solid_edicts);

		if (depth == AREA_DEPTH) {
			anode.axis = -1;
			anode.children[0] = anode.children[1] = null;
			return anode;
		}

		VectorSubtract(maxs, mins, size);
		if (size[0] > size[1])
			anode.axis = 0;
		else
			anode.axis = 1;

		anode.dist = 0.5f * (maxs[anode.axis] + mins[anode.axis]);
		VectorCopy(mins, mins1);
		VectorCopy(mins, mins2);
		VectorCopy(maxs, maxs1);
		VectorCopy(maxs, maxs2);

		maxs1[anode.axis] = mins2[anode.axis] = anode.dist;

		anode.children[0] = SV_CreateAreaNode(depth + 1, mins2, maxs2);
		anode.children[1] = SV_CreateAreaNode(depth + 1, mins1, maxs1);

		return anode;
	}

	/*
	===============
	SV_ClearWorld
	
	===============
	*/
	public static void SV_ClearWorld() {
		initNodes();
		sv_numareanodes = 0;
		SV_CreateAreaNode(0, sv.models[1].mins, sv.models[1].maxs);

		Com.Println("areanodes:" + sv_numareanodes + " (sollten 32 sein).");
		for (int n = 0; n < sv_numareanodes; n++) {
			Com.Printf(
				"|%3i|%2i|%8.2f  |%8.2f|%8.2f|%8.2f|  %8.2f|%8.2f|%8.2f|\n",
				new Vargs()
					.add(n)
					.add(sv_areanodes[n].axis)
					.add(sv_areanodes[n].dist)
					.add(sv_areanodes[n].mins_rst[0])
					.add(sv_areanodes[n].mins_rst[1])
					.add(sv_areanodes[n].mins_rst[2])
					.add(sv_areanodes[n].maxs_rst[0])
					.add(sv_areanodes[n].maxs_rst[1])
					.add(sv_areanodes[n].maxs_rst[2]));
		}
	}

	/*
	===============
	SV_UnlinkEdict
	
	===============
	*/
	public static void SV_UnlinkEdict(edict_t ent) {
		if (null == ent.area.prev)
			return; // not linked in anywhere
		RemoveLink(ent.area);
		ent.area.prev = ent.area.next = null;
	}

	/*
	===============
	SV_LinkEdict
	
	===============
	*/
	public static final int MAX_TOTAL_ENT_LEAFS = 128;

	public static void SV_LinkEdict(edict_t ent) {
		areanode_t node;
		// TODO: make static instead of new
		int leafs[] = new int[MAX_TOTAL_ENT_LEAFS];
		int clusters[] = new int[MAX_TOTAL_ENT_LEAFS];
		int num_leafs;
		int j, k;
		int area;
		int topnode = 0;

		if (ent.area.prev != null)
			SV_UnlinkEdict(ent); // unlink from old position

		if (ent == ge.edicts[0])
			return; // don't add the world

		if (!ent.inuse)
			return;

		// set the size
		VectorSubtract(ent.maxs, ent.mins, ent.size);

		// encode the size into the entity_state for client prediction
		if (ent.solid == SOLID_BBOX && 0 == (ent.svflags & SVF_DEADMONSTER)) { // assume that x/y are equal and symetric
			int i = (int) (ent.maxs[0] / 8);
			if (i < 1)
				i = 1;
			if (i > 31)
				i = 31;

			// z is not symetric
			j = (int) ((-ent.mins[2]) / 8);
			if (j < 1)
				j = 1;
			if (j > 31)
				j = 31;

			// and z maxs can be negative...
			k = (int) ((ent.maxs[2] + 32) / 8);
			if (k < 1)
				k = 1;
			if (k > 63)
				k = 63;

			ent.s.solid = (k << 10) | (j << 5) | i;
		}
		else if (ent.solid == SOLID_BSP) {
			ent.s.solid = 31; // a solid_bbox will never create this value
		}
		else
			ent.s.solid = 0;

		// set the abs box
		if (ent.solid == SOLID_BSP && (ent.s.angles[0] != 0 || ent.s.angles[1] != 0 || ent.s.angles[2] != 0)) { // expand for rotation
			float max, v;

			max = 0;
			for (int i = 0; i < 3; i++) {
				v = Math.abs(ent.mins[i]);
				if (v > max)
					max = v;
				v = Math.abs(ent.maxs[i]);
				if (v > max)
					max = v;
			}
			for (int i = 0; i < 3; i++) {
				ent.absmin[i] = ent.s.origin[i] - max;
				ent.absmax[i] = ent.s.origin[i] + max;
			}
		}
		else { // normal
			VectorAdd(ent.s.origin, ent.mins, ent.absmin);
			VectorAdd(ent.s.origin, ent.maxs, ent.absmax);
		}

		// because movement is clipped an epsilon away from an actual edge,
		// we must fully check even when bounding boxes don't quite touch

		ent.absmin[0]--;
		ent.absmin[1]--;
		ent.absmin[2]--;
		ent.absmax[0]++;
		ent.absmax[1]++;
		ent.absmax[2]++;

		// link to PVS leafs
		ent.num_clusters = 0;
		ent.areanum = 0;
		ent.areanum2 = 0;

		//get all leafs, including solids

		CM.intwrap iw = new CM.intwrap(topnode);

		num_leafs = CM.CM_BoxLeafnums(ent.absmin, ent.absmax, leafs, MAX_TOTAL_ENT_LEAFS, iw);

		topnode = iw.i;

		// set areas
		for (int i = 0; i < num_leafs; i++) {
			clusters[i] = CM.CM_LeafCluster(leafs[i]);
			area = CM.CM_LeafArea(leafs[i]);
			if (area != 0) { // doors may legally straggle two areas,
				// but nothing should evern need more than that
				if (ent.areanum != 0 && ent.areanum != area) {
					if (ent.areanum2 != 0 && ent.areanum2 != area && sv.state == ss_loading)
						Com.DPrintf("Object touching 3 areas at " + ent.absmin[0] + " " + ent.absmin[1] + " " + ent.absmin[2] + "\n");
					ent.areanum2 = area;
				}
				else
					ent.areanum = area;
			}
		}

		if (num_leafs >= MAX_TOTAL_ENT_LEAFS) { // assume we missed some leafs, and mark by headnode
			ent.num_clusters = -1;
			ent.headnode = topnode;
		}
		else {
			ent.num_clusters = 0;
			for (int i = 0; i < num_leafs; i++) {
				if (clusters[i] == -1)
					continue; // not a visible leaf
				for (j = 0; j < i; j++)
					if (clusters[j] == clusters[i])
						break;
				if (j == i) {
					if (ent.num_clusters == MAX_ENT_CLUSTERS) { // assume we missed some leafs, and mark by headnode
						ent.num_clusters = -1;
						ent.headnode = topnode;
						break;
					}

					ent.clusternums[ent.num_clusters++] = clusters[i];
				}
			}
		}

		// if first time, make sure old_origin is valid
		if (0 == ent.linkcount) {
			VectorCopy(ent.s.origin, ent.s.old_origin);
		}
		ent.linkcount++;

		if (ent.solid == SOLID_NOT)
			return;

		// find the first node that the ent's box crosses
		node = sv_areanodes[0];

		while (true) {
			if (node.axis == -1)
				break;
			if (ent.absmin[node.axis] > node.dist)
				node = node.children[0];
			else if (ent.absmax[node.axis] < node.dist)
				node = node.children[1];
			else
				break; // crosses the node
		}

		// link it in	
		if (ent.solid == SOLID_TRIGGER)
			InsertLinkBefore(ent.area, node.trigger_edicts);
		else
			InsertLinkBefore(ent.area, node.solid_edicts);

	}

	/*
	====================
	SV_AreaEdicts_r
	
	====================
	*/
	public static void SV_AreaEdicts_r(areanode_t node) {
		link_t l, next, start;
		edict_t check;
		int count;

		count = 0;

		// touch linked edicts
		if (area_type == AREA_SOLID)
			start = node.solid_edicts;
		else
			start = node.trigger_edicts;

		for (l = start.next; l != start; l = next) {
			next = l.next;
				check = //EDICT_FROM_AREA(l);
	 (edict_t) l.o;

			if (check.solid == SOLID_NOT)
				continue; // deactivated
			if (check.absmin[0] > area_maxs[0]
				|| check.absmin[1] > area_maxs[1]
				|| check.absmin[2] > area_maxs[2]
				|| check.absmax[0] < area_mins[0]
				|| check.absmax[1] < area_mins[1]
				|| check.absmax[2] < area_mins[2])
				continue; // not touching

			if (area_count == area_maxcount) {
				Com.Printf("SV_AreaEdicts: MAXCOUNT\n");
				return;
			}

			area_list[area_count] = check;
			area_count++;
		}

		if (node.axis == -1)
			return; // terminal node

		// recurse down both sides
		if (area_maxs[node.axis] > node.dist)
			SV_AreaEdicts_r(node.children[0]);

		if (area_mins[node.axis] < node.dist)
			SV_AreaEdicts_r(node.children[1]);
	}

	/*
	================
	SV_AreaEdicts
	================
	*/
	public static int SV_AreaEdicts(float[] mins, float[] maxs, edict_t list[], int maxcount, int areatype) {
		area_mins = mins;
		area_maxs = maxs;
		area_list = list;
		area_count = 0;
		area_maxcount = maxcount;
		area_type = areatype;

		SV_AreaEdicts_r(sv_areanodes[0]);
		
		/*
		Com.Printf("found edicts in area:" + area_count + "\n");
		for (int n = 0; n < area_count; n++) {
			Com.Printf("%4i : %25s", new Vargs().add(n).add(list[n].classname));
		}
		*/
		return area_count;
	}

	//===========================================================================

	/*
	=============
	SV_PointContents
	=============
	*/
	public static int SV_PointContents(float[] p) {
		// TODO: make static instead new
		edict_t touch[] = new edict_t[MAX_EDICTS], hit;
		int i, num;
		int contents, c2;
		int headnode;
		float angles[];

		// get base contents from world
		contents = CM.PointContents(p, sv.models[1].headnode);

		// or in contents from all the other entities
		num = SV_AreaEdicts(p, p, touch, MAX_EDICTS, AREA_SOLID);

		for (i = 0; i < num; i++) {
			hit = touch[i];

			// might intersect, so do an exact clip
			headnode = SV_HullForEntity(hit);
			angles = hit.s.angles;
			if (hit.solid != SOLID_BSP)
				angles = vec3_origin; // boxes don't rotate

			c2 = CM.TransformedPointContents(p, headnode, hit.s.origin, hit.s.angles);

			contents |= c2;
		}

		return contents;
	}

	/*
	================
	SV_HullForEntity
	
	Returns a headnode that can be used for testing or clipping an
	object of mins/maxs size.
	Offset is filled in to contain the adjustment that must be added to the
	testing object's origin to get a point to use with the returned hull.
	================
	*/
	public static int SV_HullForEntity(edict_t ent) {

		cmodel_t model;

		// decide which clipping hull to use, based on the size
		if (ent.solid == SOLID_BSP) { // explicit hulls in the BSP model
			model = sv.models[ent.s.modelindex];

			if (null == model)
				Com.Error(ERR_FATAL, "MOVETYPE_PUSH with a non bsp model");

			return model.headnode;
		}

		// create a temp hull from bounding box sizes

		return CM.HeadnodeForBox(ent.mins, ent.maxs);
	}

	//===========================================================================

	/*
	====================
	SV_ClipMoveToEntities
	
	====================
	*/
	public static void SV_ClipMoveToEntities(moveclip_t clip) {
		int i, num;
		// TODO: make static instead of new
		edict_t touchlist[] = new edict_t[MAX_EDICTS];
		edict_t touch;
		trace_t trace;
		int headnode;
		float angles[];

		num = SV_AreaEdicts(clip.boxmins, clip.boxmaxs, touchlist, MAX_EDICTS, AREA_SOLID);

		// be careful, it is possible to have an entity in this
		// list removed before we get to it (killtriggered)
		for (i = 0; i < num; i++) {
			touch = touchlist[i];
			if (touch.solid == SOLID_NOT)
				continue;
			if (touch == clip.passedict)
				continue;
			if (clip.trace.allsolid)
				return;
			if (clip.passedict != null) {
				if (touch.owner == clip.passedict)
					continue; // don't clip against own missiles
				if (clip.passedict.owner == touch)
					continue; // don't clip against owner
			}

			if (0 == (clip.contentmask & CONTENTS_DEADMONSTER) && 0 != (touch.svflags & SVF_DEADMONSTER))
				continue;

			// might intersect, so do an exact clip
			headnode = SV_HullForEntity(touch);
			angles = touch.s.angles;
			if (touch.solid != SOLID_BSP)
				angles = vec3_origin; // boxes don't rotate

			if ((touch.svflags & SVF_MONSTER) != 0)
				trace =
					CM.TransformedBoxTrace(
						clip.start,
						clip.end,
						clip.mins2,
						clip.maxs2,
						headnode,
						clip.contentmask,
						touch.s.origin,
						angles);
			else
				trace =
					CM.TransformedBoxTrace(
						clip.start,
						clip.end,
						clip.mins,
						clip.maxs,
						headnode,
						clip.contentmask,
						touch.s.origin,
						angles);

			if (trace.allsolid || trace.startsolid || trace.fraction < clip.trace.fraction) {
				trace.ent = touch;
				if (clip.trace.startsolid) {
					clip.trace = trace;
					clip.trace.startsolid = true;
				}
				else
					clip.trace = trace.getClone();
			}
			else if (trace.startsolid)
				clip.trace.startsolid = true;
		}
	}

	/*
	==================
	SV_TraceBounds
	==================
	*/
	public static void SV_TraceBounds(float[] start, float[] mins, float[] maxs, float[] end, float[] boxmins, float[] boxmaxs) {
		int i;

		for (i = 0; i < 3; i++) {
			if (end[i] > start[i]) {
				boxmins[i] = start[i] + mins[i] - 1;
				boxmaxs[i] = end[i] + maxs[i] + 1;
			}
			else {
				boxmins[i] = end[i] + mins[i] - 1;
				boxmaxs[i] = start[i] + maxs[i] + 1;
			}
		}

	}

	/*
	==================
	SV_Trace
	
	Moves the given mins/maxs volume through the world from start to end.
	
	Passedict and edicts owned by passedict are explicitly not checked.
	
	==================
	*/
	public static trace_t SV_Trace(float[] start, float[] mins, float[] maxs, float[] end, edict_t passedict, int contentmask) {
		moveclip_t clip = new moveclip_t();

		if (mins == null)
			mins = vec3_origin;
		if (maxs == null)
			maxs = vec3_origin;

		//memset ( clip, 0, sizeof ( moveclip_t ) );

		// clip to world
		clip.trace = CM.BoxTrace(start, end, mins, maxs, 0, contentmask);
		clip.trace.ent = ge.edicts[0];
		if (clip.trace.fraction == 0)
			return clip.trace; // blocked by the world

		clip.contentmask = contentmask;
		clip.start = start;
		clip.end = end;
		clip.mins = mins;
		clip.maxs = maxs;
		clip.passedict = passedict;

		VectorCopy(mins, clip.mins2);
		VectorCopy(maxs, clip.maxs2);

		// create the bounding box of the entire move
		SV_TraceBounds(start, clip.mins2, clip.maxs2, end, clip.boxmins, clip.boxmaxs);

		// clip to other solid entities
		SV_ClipMoveToEntities(clip);

		return clip.trace;
	}
}