//*******************************************************************************
Position HapticObject::getPosition()
{
	hduVector3Dd origin;
	hduVector3Dd pos(origin * m_transformMatrix);
	return Position(pos[0], pos[1], pos[2]);
}

void CCamera::CheckForMovement()
{
    // Once we have the frame interval, we find the current speed
    float speed = (float)(kSpeed * g_FrameInterval);

    // Before we move our camera we want to store the old position.  We then use
    // this data to test collision detection.
    CVector3 vOldPosition = Position();


/////// * /////////// * /////////// * NEW * /////// * /////////// * /////////// *

    // Store the old view vector to restore it if we collided backwards
    CVector3 vOldView = View();

    // Use a flag to see if we movement backwards or not
    bool bMovedBack = false;

/////// * /////////// * /////////// * NEW * /////// * /////////// * /////////// *


    // Check if we hit the Up arrow or the 'w' key
    if(GetKeyState(VK_UP) & 0x80 || GetKeyState('W') & 0x80)
    {

        // Move our camera forward by a positive SPEED
        MoveCamera(speed);
    }

    // Check if we hit the Down arrow or the 's' key
    if(GetKeyState(VK_DOWN) & 0x80 || GetKeyState('S') & 0x80)
    {

        // Move our camera backward by a negative SPEED
        MoveCamera(-speed);
        bMovedBack = true;
    }

    // Check if we hit the Left arrow or the 'a' key
    if(GetKeyState(VK_LEFT) & 0x80 || GetKeyState('A') & 0x80)
    {

        // Strafe the camera left
        StrafeCamera(-speed);
    }

    // Check if we hit the Right arrow or the 'd' key
    if(GetKeyState(VK_RIGHT) & 0x80 || GetKeyState('D') & 0x80)
    {

        // Strafe the camera right
        StrafeCamera(speed);
    }

    // Now that we moved, let's get the current position and test our movement
    // vector against the level data to see if there is a collision.
    CVector3 vCurrentPosition = Position();

    // We will not use sphere collision from now on, but AABB collision (box)
//	CVector3 vNewPosition = g_Level.TraceSphere(vOldPosition, vCurrentPosition, 25.0f);


/////// * /////////// * /////////// * NEW * /////// * /////////// * /////////// *

    // We are now using AABB collision now, so we no longer use sphere checks.
    // Below we pass into the TraceBox() function some generic Min and Max values
    // for our bounding box.  We then get the new position if we collided
    CVector3 vNewPosition = g_Level.TraceBox(vOldPosition, vCurrentPosition,
                            CVector3(-20, -50, -20), CVector3(20, 50, 20));

    // We add some code below to make it so when we back into a wall, our view vector
    // doesn't keep going backwards, since we aren't moving backwards.  If we don't
    // do this check, it will turn our camera around and look like a glitch.  Not desired!

    // Check if we collided and we moved backwards
    if(g_Level.Collided() && bMovedBack)
    {
        // If or x or y didn't move, then we are backed into a wall so restore the view vector
        if(vNewPosition.x == vOldPosition.x || vNewPosition.z == vOldPosition.z)
            m_vView = vOldView;
    }

/////// * /////////// * /////////// * NEW * /////// * /////////// * /////////// *


    // Set the new position that was returned from our trace function
    m_vPosition = vNewPosition;
}

bool Spawns::parseSpawnNode(xmlNodePtr p, bool checkDuplicate)
{
	if(xmlStrcmp(p->name, (const xmlChar*)"spawn"))
		return false;

	int32_t intValue;
	std::string strValue;

	Position centerPos;
	if(!readXMLString(p, "centerpos", strValue))
	{
		if(!readXMLInteger(p, "centerx", intValue))
			return false;

		centerPos.x = intValue;
		if(!readXMLInteger(p, "centery", intValue))
			return false;

		centerPos.y = intValue;
		if(!readXMLInteger(p, "centerz", intValue))
			return false;

		centerPos.z = intValue;
	}
	else
	{
		IntegerVec posVec = vectorAtoi(explodeString(strValue, ","));
		if(posVec.size() < 3)
			return false;

		centerPos = Position(posVec[0], posVec[1], posVec[2]);
	}

	if(!readXMLInteger(p, "radius", intValue))
		return false;

	int32_t radius = intValue;
	Spawn* spawn = new Spawn(centerPos, radius);
	if(checkDuplicate)
	{
		for(SpawnList::iterator it = spawnList.begin(); it != spawnList.end(); ++it)
		{
			if((*it)->getPosition() == centerPos)
				delete *it;
		}
	}

	spawnList.push_back(spawn);
	for(xmlNodePtr tmpNode = p->children; tmpNode; tmpNode = tmpNode->next)
	{
		if(!xmlStrcmp(tmpNode->name, (const xmlChar*)"monster"))
		{
			if(!readXMLString(tmpNode, "name", strValue))
				continue;

			std::string name = strValue;
			int32_t interval = MINSPAWN_INTERVAL / 1000;
			if(readXMLInteger(tmpNode, "spawntime", intValue) || readXMLInteger(tmpNode, "interval", intValue))
			{
				if(intValue <= interval)
				{
					std::clog << "[Warning - Spawns::loadFromXml] " << name << " " << centerPos << " spawntime cannot"
						<< " be less than " << interval << " seconds." << std::endl;
					continue;
				}

				interval = intValue;
			}

			interval *= 1000;
			Position placePos = centerPos;
			if(readXMLInteger(tmpNode, "x", intValue))
				placePos.x += intValue;

			if(readXMLInteger(tmpNode, "y", intValue))
				placePos.y += intValue;

			if(readXMLInteger(tmpNode, "z", intValue))
				placePos.z /*+*/= intValue;

			Direction direction = NORTH;
			if(readXMLInteger(tmpNode, "direction", intValue) && direction >= EAST && direction <= WEST)
				direction = (Direction)intValue;

			spawn->addMonster(name, placePos, direction, interval);
		}
		else if(!xmlStrcmp(tmpNode->name, (const xmlChar*)"npc"))
		{
			if(!readXMLString(tmpNode, "name", strValue))
				continue;

			std::string name = strValue;
			Position placePos = centerPos;
			if(readXMLInteger(tmpNode, "x", intValue))
				placePos.x += intValue;

			if(readXMLInteger(tmpNode, "y", intValue))
				placePos.y += intValue;

			if(readXMLInteger(tmpNode, "z", intValue))
//.........这里部分代码省略.........

/* Test the method 'move2side'*/
TEST_F(PositionVectorTest, test_method_move2side) {	
    PositionVector vec1;
    vec1.push_back(Position(0,1,0));
    vec1.push_back(Position(0,0,0));
    vec1.push_back(Position(1,0,0));
    vec1.move2side(.5);
    EXPECT_EQ(Position(-.5,1), vec1[0]);
    EXPECT_EQ(Position(-.5,-.5), vec1[1]);
    EXPECT_EQ(Position(1,-.5), vec1[2]);
    vec1.move2side(-1);
    EXPECT_EQ(Position(.5,1), vec1[0]);
    EXPECT_EQ(Position(.5,.5), vec1[1]);
    EXPECT_EQ(Position(1,.5), vec1[2]);

    // parallel case
    PositionVector vec2;
    vec2.push_back(Position(0,0,0));
    vec2.push_back(Position(1,0,0));
    vec2.push_back(Position(3,0,0));
    vec2.move2side(.5);
    EXPECT_EQ(Position(0,-.5), vec2[0]);
    EXPECT_EQ(Position(1,-.5), vec2[1]);
    EXPECT_EQ(Position(3,-.5), vec2[2]);
    vec2.move2side(-1);
    EXPECT_EQ(Position(0,.5), vec2[0]);
    EXPECT_EQ(Position(1,.5), vec2[1]);
    EXPECT_EQ(Position(3,.5), vec2[2]);

    // counterparallel case
    {
    PositionVector vec3;
    vec3.push_back(Position(0,0,0));
    vec3.push_back(Position(3,0,0));
    vec3.push_back(Position(1,0,0));
    vec3.move2side(.5);
    EXPECT_EQ(Position(0,-.5), vec3[0]);
    EXPECT_EQ(Position(3.5,0), vec3[1]);
    EXPECT_EQ(Position(1,.5), vec3[2]);
    }
    /*{
    PositionVector vec3;
    vec3.push_back(Position(0,0,0));
    vec3.push_back(Position(3,0,0));
    vec3.push_back(Position(1,0,0));
    vec3.move2side(-.5);
    EXPECT_EQ(Position(0,-.5), vec3[0]);
    EXPECT_EQ(Position(3.5,0), vec3[1]);
    EXPECT_EQ(Position(1,.5), vec3[2]);
    }*/
}

NS_IMETHODIMP
HTMLProgressElement::GetPosition(double* aPosition)
{
  *aPosition = Position();
  return NS_OK;
}

bool Spawns::loadFromXml(const std::string& _filename)
{
	if (loaded) {
		return true;
	}

	pugi::xml_document doc;
	pugi::xml_parse_result result = doc.load_file(_filename.c_str());
	if (!result) {
		printXMLError("Error - Spawns::loadFromXml", _filename, result);
		return false;
	}

	filename = _filename;
	loaded = true;

	for (auto spawnNode : doc.child("spawns").children()) {
		Position centerPos(
			pugi::cast<uint16_t>(spawnNode.attribute("centerx").value()),
			pugi::cast<uint16_t>(spawnNode.attribute("centery").value()),
			pugi::cast<uint16_t>(spawnNode.attribute("centerz").value())
		);

		int32_t radius;
		pugi::xml_attribute radiusAttribute = spawnNode.attribute("radius");
		if (radiusAttribute) {
			radius = pugi::cast<int32_t>(radiusAttribute.value());
		} else {
			radius = -1;
		}

		spawnList.emplace_front(centerPos, radius);
		Spawn& spawn = spawnList.front();

		for (auto childNode : spawnNode.children()) {
			if (strcasecmp(childNode.name(), "monster") == 0) {
				pugi::xml_attribute nameAttribute = childNode.attribute("name");
				if (!nameAttribute) {
					continue;
				}

				Direction dir;

				pugi::xml_attribute directionAttribute = childNode.attribute("direction");
				if (directionAttribute) {
					dir = static_cast<Direction>(pugi::cast<uint16_t>(directionAttribute.value()));
				} else {
					dir = DIRECTION_NORTH;
				}

				Position pos(
					centerPos.x + pugi::cast<uint16_t>(childNode.attribute("x").value()),
					centerPos.y + pugi::cast<uint16_t>(childNode.attribute("y").value()),
					centerPos.z
				);
				uint32_t interval = pugi::cast<uint32_t>(childNode.attribute("spawntime").value()) * 1000;
				if (interval > MINSPAWN_INTERVAL) {
					spawn.addMonster(nameAttribute.as_string(), pos, dir, interval);
				} else {
					std::cout << "[Warning - Spawns::loadFromXml] " << nameAttribute.as_string() << ' ' << pos << " spawntime can not be less than " << MINSPAWN_INTERVAL / 1000 << " seconds." << std::endl;
				}
			} else if (strcasecmp(childNode.name(), "npc") == 0) {
				pugi::xml_attribute nameAttribute = childNode.attribute("name");
				if (!nameAttribute) {
					continue;
				}

				Npc* npc = Npc::createNpc(nameAttribute.as_string());
				if (!npc) {
					continue;
				}

				pugi::xml_attribute directionAttribute = childNode.attribute("direction");
				if (directionAttribute) {
					npc->setDirection(static_cast<Direction>(pugi::cast<uint16_t>(directionAttribute.value())));
				}

				npc->setMasterPos(Position(
					centerPos.x + pugi::cast<uint16_t>(childNode.attribute("x").value()),
					centerPos.y + pugi::cast<uint16_t>(childNode.attribute("y").value()),
					centerPos.z
				), radius);
				npcList.push_front(npc);
			}
		}
	}
	return true;
}

bool Monster::getDanceStep(const Position& creaturePos, Direction& dir,	bool keepAttack /*= true*/, bool keepDistance /*= true*/)
{
	assert(attackedCreature);
	bool canDoAttackNow = canUseAttack(creaturePos, attackedCreature);
	const Position& centerPos = attackedCreature->getPosition();

	uint32_t tmpDist, centerToDist = std::max(std::abs(creaturePos.x - centerPos.x), std::abs(creaturePos.y - centerPos.y));
	DirVector dirVector;
	if(!keepDistance || creaturePos.y - centerPos.y >= 0)
	{
		tmpDist = std::max(std::abs((creaturePos.x) - centerPos.x), std::abs((creaturePos.y - 1) - centerPos.y));
		if(tmpDist == centerToDist && canWalkTo(creaturePos, NORTH))
		{
			bool result = true;
			if(keepAttack)
				result = (!canDoAttackNow || canUseAttack(Position(creaturePos.x, creaturePos.y - 1, creaturePos.z), attackedCreature));

			if(result)
				dirVector.push_back(NORTH);
		}
	}

	if(!keepDistance || creaturePos.y - centerPos.y <= 0)
	{
		tmpDist = std::max(std::abs((creaturePos.x) - centerPos.x), std::abs((creaturePos.y + 1) - centerPos.y));
		if(tmpDist == centerToDist && canWalkTo(creaturePos, SOUTH))
		{
			bool result = true;
			if(keepAttack)
				result = (!canDoAttackNow || canUseAttack(Position(creaturePos.x, creaturePos.y + 1, creaturePos.z), attackedCreature));

			if(result)
				dirVector.push_back(SOUTH);
		}
	}

	if(!keepDistance || creaturePos.x - centerPos.x >= 0)
	{
		tmpDist = std::max(std::abs((creaturePos.x + 1) - centerPos.x), std::abs((creaturePos.y) - centerPos.y));
		if(tmpDist == centerToDist && canWalkTo(creaturePos, EAST))
		{
			bool result = true;
			if(keepAttack)
				result = (!canDoAttackNow || canUseAttack(Position(creaturePos.x + 1, creaturePos.y, creaturePos.z), attackedCreature));

			if(result)
				dirVector.push_back(EAST);
		}
	}

	if(!keepDistance || creaturePos.x - centerPos.x <= 0)
	{
		tmpDist = std::max(std::abs((creaturePos.x - 1) - centerPos.x), std::abs((creaturePos.y) - centerPos.y));
		if(tmpDist == centerToDist && canWalkTo(creaturePos, WEST))
		{
			bool result = true;
			if(keepAttack)
				result = (!canDoAttackNow || canUseAttack(Position(creaturePos.x - 1, creaturePos.y, creaturePos.z), attackedCreature));

			if(result)
				dirVector.push_back(WEST);
		}
	}

	if(dirVector.empty())
		return false;

	std::random_shuffle(dirVector.begin(), dirVector.end());
	dir = dirVector[random_range(0, dirVector.size() - 1)];
	return true;
}

	void Render(double time)
	{
		gl.Clear().ColorBuffer().DepthBuffer();
		//
		auto camera = CamMatrixf::Orbiting(
			Vec3f(0.0, 1.5, 0.0),
			7.0 + SineWave(time / 11.0)*1.5,
			FullCircles(time / 19.0),
			Degrees(SineWave(time / 20.0) * 30 + 35)
		);
		cube_prog.camera_matrix = camera;
		cube_prog.camera_position = camera.Position();


		// shiny gray/blue checkered cube
		cube_prog.frag_subroutines.Apply(cube_prog.frag_shiny_checker);

		cube_prog.specular_factor = 32;
		cube_prog.color_1 = Vec3f(0.9, 0.8, 0.7);
		cube_prog.color_2 = Vec3f(0.3, 0.4, 0.5);
		cube_prog.tex_scale = Vec2f(4, 4);
		cube_prog.model_matrix =
			ModelMatrixf::RotationY(FullCircles(time / 7.0))*
			ModelMatrixf::Translation( 2.0, 0.0, 0.0)*
			ModelMatrixf::RotationX(Degrees(25 * time));
		cube.Draw();

		// shiny textured cube
		cube_prog.frag_subroutines.Apply(cube_prog.frag_shiny_texture);

		cube_prog.specular_factor = 16;
		cube_prog.tex_scale = Vec2f(1, 1);
		cube_prog.model_matrix =
			ModelMatrixf::RotationY(FullCircles(time / 7.0))*
			ModelMatrixf::Translation(-2.0, 0.0, 0.0)*
			ModelMatrixf::RotationX(Degrees(-17 * time));
		cube.Draw();

		// shiny yellow/black striped cube
		cube_prog.frag_subroutines.Apply(cube_prog.frag_shiny_strips);

		cube_prog.specular_factor = 32;
		cube_prog.color_1 = Vec3f(0.9, 0.9, 0.1);
		cube_prog.color_2 = Vec3f(0.1, 0.1, 0.1);
		cube_prog.tex_scale = Vec2f(16, 16);
		cube_prog.model_matrix =
			ModelMatrixf::RotationY(FullCircles(time / 7.0))*
			ModelMatrixf::Translation( 0.0, 2.0, 0.0)*
			ModelMatrixf::RotationY(Degrees(37 * time));
		cube.Draw();

		// shiny gray/green spiral cube
		cube_prog.frag_subroutines.Apply(cube_prog.frag_shiny_spiral);

		cube_prog.specular_factor = 24;
		cube_prog.color_1 = Vec3f(0.9, 0.9, 0.9);
		cube_prog.color_2 = Vec3f(0.4, 0.9, 0.4);
		cube_prog.tex_scale = Vec2f(1, 1);
		cube_prog.model_matrix =
			ModelMatrixf::RotationY(FullCircles(time / 7.0))*
			ModelMatrixf::Translation( 0.0,-2.0, 0.0)*
			ModelMatrixf::RotationY(Degrees(-13 * time));
		cube.Draw();

		// dull white/red striped cube
		cube_prog.frag_subroutines
			.Assign(
				cube_prog.pixel_light_func,
				cube_prog.dull
			).Assign(
				cube_prog.pixel_color_func,
				cube_prog.strips
			).Apply();

		cube_prog.specular_factor = 32;
		cube_prog.color_2 = Vec3f(1.0, 1.0, 1.0);
		cube_prog.color_1 = Vec3f(0.9, 0.2, 0.2);
		cube_prog.tex_scale = Vec2f(8, 6);
		cube_prog.model_matrix =
			ModelMatrixf::RotationY(FullCircles(time / 7.0))*
			ModelMatrixf::Translation( 0.0, 0.0, 2.0)*
			ModelMatrixf::RotationZ(Degrees(27 * time));
		cube.Draw();

		// dull textured cube
		cube_prog.frag_subroutines
			.Assign(
				cube_prog.pixel_color_func,
				cube_prog.texture_bgr
			).Apply();

		cube_prog.tex_scale = Vec2f(1, 1);
		cube_prog.model_matrix =
			ModelMatrixf::RotationY(FullCircles(time / 7.0))*
			ModelMatrixf::Translation( 0.0, 0.0,-2.0)*
			ModelMatrixf::RotationZ(Degrees(-23 * time));
		cube.Draw();
	}

/**
 * Calculates the effects of the explosion.
 */
void ExplosionBState::explode()
{
	bool terrainExplosion = false;
	SavedBattleGame *save = _parent->getSave();
	// after the animation is done, the real explosion/hit takes place
	if (_item)
	{
		if (!_unit && _item->getPreviousOwner())
		{
			_unit = _item->getPreviousOwner();
		}

		BattleUnit *victim = 0;

		if (_areaOfEffect)
		{
			save->getTileEngine()->explode(_center, _power, _item->getRules()->getDamageType(), _item->getRules()->getExplosionRadius(), _unit);
		}
		else if (!_cosmetic)
		{
			ItemDamageType type = _item->getRules()->getDamageType();

			victim = save->getTileEngine()->hit(_center, _power, type, _unit);
		}
		// check if this unit turns others into zombies
		if (!_item->getRules()->getZombieUnit().empty()
			&& victim
			&& victim->getArmor()->getSize() == 1
			&& (victim->getGeoscapeSoldier() || victim->getUnitRules()->getRace() == "STR_CIVILIAN")
			&& victim->getSpawnUnit().empty())
		{
			// converts the victim to a zombie on death
			victim->setRespawn(true);
			victim->setSpawnUnit(_item->getRules()->getZombieUnit());
		}
	}
	if (_tile)
	{
		ItemDamageType DT;
		switch (_tile->getExplosiveType())
		{
		case 0:
			DT = DT_HE;
			break;
		case 5:
			DT = DT_IN;
			break;
		case 6:
			DT = DT_STUN;
			break;
		default:
			DT = DT_SMOKE;
			break;
		}
		if (DT != DT_HE)
		{
			_tile->setExplosive(0,0,true);
		}
		save->getTileEngine()->explode(_center, _power, DT, _power/10);
		terrainExplosion = true;
	}
	if (!_tile && !_item)
	{
		int radius = 6;
		// explosion not caused by terrain or an item, must be by a unit (cyberdisc)
		if (_unit && (_unit->getSpecialAbility() == SPECAB_EXPLODEONDEATH || _unit->getSpecialAbility() == SPECAB_BURN_AND_EXPLODE))
		{
			radius = _parent->getMod()->getItem(_unit->getArmor()->getCorpseGeoscape(), true)->getExplosionRadius();
		}
		save->getTileEngine()->explode(_center, _power, DT_HE, radius);
		terrainExplosion = true;
	}

	if (!_cosmetic)
	{
		// now check for new casualties
		_parent->checkForCasualties(_item, _unit, false, terrainExplosion);
	}

	// if this explosion was caused by a unit shooting, now it's the time to put the gun down
	if (_unit && !_unit->isOut() && _lowerWeapon)
	{
		_unit->aim(false);
		_unit->setCache(0);
	}
	_parent->getMap()->cacheUnits();
	_parent->popState();

	// check for terrain explosions
	Tile *t = save->getTileEngine()->checkForTerrainExplosions();
	if (t)
	{
		Position p = Position(t->getPosition().x * 16, t->getPosition().y * 16, t->getPosition().z * 24);
		p += Position(8,8,0);
		_parent->statePushFront(new ExplosionBState(_parent, p, 0, _unit, t));
	}

//.........这里部分代码省略.........

 * 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, see <http://www.gnu.org/licenses/>.
 */

#include "ScriptMgr.h"
#include "ScriptedCreature.h"
#include "InstanceScript.h"
#include "naxxramas.h"

BossBoundaryData const boundaries =
{
    /* Arachnid Quarter */
    { BOSS_ANUBREKHAN, new CircleBoundary(Position(3273.376709f, -3475.876709f), Position(3195.668213f, -3475.930176f)) },
    { BOSS_FAERLINA, new RectangleBoundary(3315.0f, 3402.0f, -3727.0f, -3590.0f) },
    { BOSS_FAERLINA, new CircleBoundary(Position(3372.68f, -3648.2f), Position(3316.0f, -3704.26f)) },
    { BOSS_MAEXXNA, new CircleBoundary(Position(3502.2587f, -3892.1697f), Position(3418.7422f, -3840.271f)) },

    /* Plague Quarter */
    { BOSS_NOTH, new RectangleBoundary(2618.0f, 2754.0f, -3557.43f, -3450.0f) },
    { BOSS_HEIGAN, new CircleBoundary(Position(2772.57f, -3685.28f), 56.0f) },
    { BOSS_LOATHEB, new CircleBoundary(Position(2909.0f, -3997.41f), 57.0f) },

    /* Military Quarter */
    { BOSS_RAZUVIOUS, new ZRangeBoundary(260.0f, 287.0f) }, // will not chase onto the upper floor
    { BOSS_GOTHIK, new RectangleBoundary(2627.0f, 2764.0f, -3440.0f, -3275.0f) },
    { BOSS_HORSEMEN, new ParallelogramBoundary(AreaBoundary::DoublePosition(2646.0, -2959.0), AreaBoundary::DoublePosition(2529.0, -3075.0), AreaBoundary::DoublePosition(2506.0, -2854.0)) },

    /* Construct Quarter */

Physics::CollisionType Physics::checkCollision(
    const Body &a,
    const Body &b
) {
    const Position &pa = a.getPosition();
    const Position &pb = b.getPosition();
    const BoundingVolume &va = a.getBounds();
    const BoundingVolume &vb = b.getBounds();

    if (va.getType() == vb.getType()) {
        switch (va.getType()) {
            case BoundingVolume::AABB: {
                // box <-> box collision test
                Position minA = pa - Position(va.getDimensions());
                Position maxA = pa + Position(va.getDimensions());
                Position minB = pb - Position(vb.getDimensions());
                Position maxB = pb + Position(vb.getDimensions());

                if (
                    minA.x <= maxB.x + Epsilon && minA.y <= maxB.y + Epsilon && minA.z <= maxB.z + Epsilon &&
                    minB.x <= maxA.x + Epsilon && minB.y <= maxA.y + Epsilon && minB.z <= maxA.z + Epsilon
                ) {
                    if (
                        minA.x < maxB.x - Epsilon && minA.y < maxB.y - Epsilon && minA.z < maxB.z - Epsilon &&
                        minB.x < maxA.x - Epsilon && minB.y < maxA.y - Epsilon && minB.z < maxA.z - Epsilon
                    ) {
                        return CollisionType::Intrusion;
                    } else {
                        return CollisionType::Contact;
                    }
                } else {
                    return CollisionType::None;
                }
            }

            case BoundingVolume::Sphere: {
                // sphere <-> sphere collision test
                Position c = pb - pa;
                LargeDelta r = vb.getRadius() + va.getRadius();
                HugeDelta d = c.x * c.x + c.y * c.y + c.z * c.z - r * r;

                if (d >= Epsilon) {
                    return CollisionType::None;
                } else if (d > -Epsilon) {
                    return CollisionType::Contact;
                } else {
                    return CollisionType::Intrusion;
                }
            }

            case BoundingVolume::Capsule: {
                // capsule <-> capsule collision test
                Position c = pb - pa;
                LargeDelta r = vb.getRadius() + va.getRadius();
                //~ LargeDelta h = b.getHeight() + a.getHeight() - r;
                HugeDelta d = c.x * c.x + c.z * c.z - r * r;

                if (d >= Epsilon) {
                    // out of horizontal range, no need to check vertical
                    return CollisionType::None;
                } else if (d > -Epsilon) {
                    //! @todo vertical contact test
                    return CollisionType::Contact;
                } else {
                    //! @todo vertical intrusion test
                    return CollisionType::Intrusion;
                }
            }
        }
    } else {
        if (va.getType() == BoundingVolume::AABB && vb.getType() == BoundingVolume::Sphere) {
            //! @todo box <-> sphere collision test
        } else if (va.getType() == BoundingVolume::Sphere && vb.getType() == BoundingVolume::AABB) {
            //! @todo sphere <-> box collision test
        } else if (va.getType() == BoundingVolume::AABB && vb.getType() == BoundingVolume::Capsule) {
            //! @todo box <-> capsule collision test
        } else if (va.getType() == BoundingVolume::Capsule && vb.getType() == BoundingVolume::AABB) {
            //! @todo capsule <-> box collision test
        } else if (va.getType() == BoundingVolume::Sphere && vb.getType() == BoundingVolume::Capsule) {
            //! @todo sphere <-> capsule collision test
        } else if (va.getType() == BoundingVolume::Capsule && vb.getType() == BoundingVolume::Sphere) {
            //! @todo capsule <-> sphere collision test
        }
    }

    // no collision, or no test for given bounding volumes
    sf::err() << "no collision test for given bounding volumes (" <<
        va.getType() << ", " << vb.getType() << ")\n";
    return CollisionType::None;
}

void Physics::update(Body &b, const sf::Time &t) const {
    float s = t.asSeconds();
    b.mPosition += Position(b.mVelocity.x * s, b.mVelocity.y * s, b.mVelocity.z * s);
}

void InsertTextCommand::doApply()
{
    ASSERT(m_text.find('\n') == notFound);

    if (!endingSelection().isNonOrphanedCaretOrRange())
        return;

    // Delete the current selection.
    // FIXME: This delete operation blows away the typing style.
    if (endingSelection().isRange()) {
        if (performTrivialReplace(m_text, m_selectInsertedText))
            return;
        deleteSelection(false, true, true, false);
        // deleteSelection eventually makes a new endingSelection out of a Position. If that Position doesn't have
        // a renderer (e.g. it is on a <frameset> in the DOM), the VisibleSelection cannot be canonicalized to 
        // anything other than NoSelection. The rest of this function requires a real endingSelection, so bail out.
        if (endingSelection().isNone())
            return;
    }

    Position startPosition(endingSelection().start());
    
    Position placeholder;
    // We want to remove preserved newlines and brs that will collapse (and thus become unnecessary) when content 
    // is inserted just before them.
    // FIXME: We shouldn't really have to do this, but removing placeholders is a workaround for 9661.
    // If the caret is just before a placeholder, downstream will normalize the caret to it.
    Position downstream(startPosition.downstream());
    if (lineBreakExistsAtPosition(downstream)) {
        // FIXME: This doesn't handle placeholders at the end of anonymous blocks.
        VisiblePosition caret(startPosition);
        if (isEndOfBlock(caret) && isStartOfParagraph(caret))
            placeholder = downstream;
        // Don't remove the placeholder yet, otherwise the block we're inserting into would collapse before
        // we get a chance to insert into it.  We check for a placeholder now, though, because doing so requires
        // the creation of a VisiblePosition, and if we did that post-insertion it would force a layout.
    }
    
    // Insert the character at the leftmost candidate.
    startPosition = startPosition.upstream();
    
    // It is possible for the node that contains startPosition to contain only unrendered whitespace,
    // and so deleteInsignificantText could remove it.  Save the position before the node in case that happens.
    Position positionBeforeStartNode(positionInParentBeforeNode(startPosition.containerNode()));
    deleteInsignificantText(startPosition.upstream(), startPosition.downstream());
    if (!startPosition.anchorNode()->inDocument())
        startPosition = positionBeforeStartNode;
    if (!startPosition.isCandidate())
        startPosition = startPosition.downstream();
    
    startPosition = positionAvoidingSpecialElementBoundary(startPosition);
    
    Position endPosition;
    
    if (m_text == "\t") {
        endPosition = insertTab(startPosition);
        startPosition = endPosition.previous();
        if (placeholder.isNotNull())
            removePlaceholderAt(placeholder);
    } else {
        // Make sure the document is set up to receive m_text
        startPosition = positionInsideTextNode(startPosition);
        ASSERT(startPosition.anchorType() == Position::PositionIsOffsetInAnchor);
        ASSERT(startPosition.containerNode());
        ASSERT(startPosition.containerNode()->isTextNode());
        if (placeholder.isNotNull())
            removePlaceholderAt(placeholder);
        RefPtr<Text> textNode = startPosition.containerText();
        const unsigned offset = startPosition.offsetInContainerNode();

        insertTextIntoNode(textNode, offset, m_text);
        endPosition = Position(textNode, offset + m_text.length());

        if (m_rebalanceType == RebalanceLeadingAndTrailingWhitespaces) {
            // The insertion may require adjusting adjacent whitespace, if it is present.
            rebalanceWhitespaceAt(endPosition);
            // Rebalancing on both sides isn't necessary if we've inserted only spaces.
            if (!shouldRebalanceLeadingWhitespaceFor(m_text))
                rebalanceWhitespaceAt(startPosition);
        } else {
            ASSERT(m_rebalanceType == RebalanceAllWhitespaces);
            if (canRebalance(startPosition) && canRebalance(endPosition))
                rebalanceWhitespaceOnTextSubstring(textNode, startPosition.offsetInContainerNode(), endPosition.offsetInContainerNode());
        }
    }

    // We could have inserted a part of composed character sequence,
    // so we are basically treating ending selection as a range to avoid validation.
    // <http://bugs.webkit.org/show_bug.cgi?id=15781>
    VisibleSelection forcedEndingSelection;
    forcedEndingSelection.setWithoutValidation(startPosition, endPosition);
    forcedEndingSelection.setIsDirectional(endingSelection().isDirectional());
    setEndingSelection(forcedEndingSelection);

    // Handle the case where there is a typing style.
    if (RefPtr<EditingStyle> typingStyle = document()->frame()->selection()->typingStyle()) {
        typingStyle->prepareToApplyAt(endPosition, EditingStyle::PreserveWritingDirection);
        if (!typingStyle->isEmpty())
            applyStyle(typingStyle.get());
    }
//.........这里部分代码省略.........

C *PosSearch<C>::FindNearest(const Point &pos, const Rect16 &area, F IsValid, F2 Position)
{
    int right_pos = NewFind(pos.x);
    int left_pos = right_pos - 1;
    int max_dist = INT_MAX;
    C *closest = nullptr;
    bool cont = true;
    while (cont)
    {
        cont = false;
        if (left_pos >= 0)
        {
            int left = left_positions[left_pos];
            int widest_right = left + max_width;
            if (widest_right < area.left || pos.x - widest_right > max_dist)
                left_pos = -1;
            else
            {
                cont = true;
                C *value = &left_to_value[left_pos];
                Point val_pos = Position(*value);
                if (val_pos.y < area.bottom && val_pos.y >= area.top && val_pos.x >= area.left)
                {
                    if (IsValid(*value))
                    {
                        int dist = Distance(pos, val_pos);
                        if (dist < max_dist)
                        {
                            closest = value;
                            max_dist = dist;
                        }
                    }
                }
                left_pos--;
            }
        }
        if (right_pos < (int)Size())
        {
            int right = left_to_right[right_pos];
            int widest_left = right - max_width;
            if (widest_left > area.right || widest_left - pos.x > max_dist)
                right_pos = Size();
            else
            {
                cont = true;
                C *value = &left_to_value[right_pos];
                Point val_pos = Position(*value);
                if (val_pos.y < area.bottom && val_pos.y >= area.top && val_pos.x < area.right)
                {
                    if (IsValid(*value))
                    {
                        int dist = Distance(pos, val_pos);
                        if (dist < max_dist)
                        {
                            closest = value;
                            max_dist = dist;
                        }
                    }
                }
                right_pos++;
            }
        }
    }
    return closest;
}

drape_ptr<LayerRenderer> LayerCacher::RecacheDebugLabels(ref_ptr<dp::TextureManager> textures)
{
  drape_ptr<LayerRenderer> renderer = make_unique_dp<LayerRenderer>();

  float const vs = df::VisualParams::Instance().GetVisualScale();
  DebugInfoLabels debugLabels = DebugInfoLabels(Position(m2::PointF(10.0f * vs, 50.0f * vs), dp::Center));

  debugLabels.AddLabel(textures, "visible: km2, readed: km2, ratio:",
                       [](ScreenBase const & screen, string & content) -> bool
  {
    double const sizeX = screen.PixelRectIn3d().SizeX();
    double const sizeY = screen.PixelRectIn3d().SizeY();

    m2::PointD const p0 = screen.PtoG(screen.P3dtoP(m2::PointD(0.0, 0.0)));
    m2::PointD const p1 = screen.PtoG(screen.P3dtoP(m2::PointD(0.0, sizeY)));
    m2::PointD const p2 = screen.PtoG(screen.P3dtoP(m2::PointD(sizeX, sizeY)));
    m2::PointD const p3 = screen.PtoG(screen.P3dtoP(m2::PointD(sizeX, 0.0)));

    double const areaG = MercatorBounds::AreaOnEarth(p0, p1, p2) +
        MercatorBounds::AreaOnEarth(p2, p3, p0);

    double const sizeX_2d = screen.PixelRect().SizeX();
    double const sizeY_2d = screen.PixelRect().SizeY();

    m2::PointD const p0_2d = screen.PtoG(m2::PointD(0.0, 0.0));
    m2::PointD const p1_2d = screen.PtoG(m2::PointD(0.0, sizeY_2d));
    m2::PointD const p2_2d = screen.PtoG(m2::PointD(sizeX_2d, sizeY_2d));
    m2::PointD const p3_2d = screen.PtoG(m2::PointD(sizeX_2d, 0.0));

    double const areaGTotal = MercatorBounds::AreaOnEarth(p0_2d, p1_2d, p2_2d) +
        MercatorBounds::AreaOnEarth(p2_2d, p3_2d, p0_2d);

    ostringstream out;
    out << fixed << setprecision(2)
        << "visible: " << areaG / 1000000.0 << " km2"
        << ", readed: " << areaGTotal / 1000000.0 << " km2"
        << ", ratio: " << areaGTotal / areaG;
    content.assign(out.str());
    return true;
  });

  debugLabels.AddLabel(textures, "scale2d: m/px, scale2d * vs: m/px",
                       [](ScreenBase const & screen, string & content) -> bool
  {
    double const distanceG = MercatorBounds::DistanceOnEarth(screen.PtoG(screen.PixelRect().LeftBottom()),
                                                            screen.PtoG(screen.PixelRect().RightBottom()));

    double const vs = df::VisualParams::Instance().GetVisualScale();
    double const scale = distanceG / screen.PixelRect().SizeX();

    ostringstream out;
    out << fixed << setprecision(2)
        << "scale2d: " << scale << " m/px"
        << ", scale2d * vs: " << scale * vs << " m/px";
    content.assign(out.str());
    return true;
  });

  debugLabels.AddLabel(textures, "distance: m",
                       [](ScreenBase const & screen, string & content) -> bool
  {
    double const sizeX = screen.PixelRectIn3d().SizeX();
    double const sizeY = screen.PixelRectIn3d().SizeY();

    double const distance = MercatorBounds::DistanceOnEarth(screen.PtoG(screen.P3dtoP(m2::PointD(sizeX / 2.0, 0.0))),
                                                            screen.PtoG(screen.P3dtoP(m2::PointD(sizeX / 2.0, sizeY))));

    ostringstream out;
    out << fixed << setprecision(2)
        << "distance: " << distance << " m";
    content.assign(out.str());
    return true;
  });

  debugLabels.AddLabel(textures, "angle: ",
                       [](ScreenBase const & screen, string & content) -> bool
  {
    ostringstream out;
    out << fixed << setprecision(2)
        << "angle: " << screen.GetRotationAngle() * 180.0 / math::pi;
    content.assign(out.str());
    return true;
  });

  renderer->AddShapeRenderer(WIDGET_DEBUG_INFO, debugLabels.Draw(textures));

  // Flush gui geometry.
  GLFunctions::glFlush();

  return renderer;
}

/**
 * calculateTrajectory.
 * @return true when a trajectory is possible.
 */
bool Projectile::calculateThrow(double accuracy)
{
	Position originVoxel, targetVoxel;
	bool foundCurve = false;

	// object blocking - can't throw here
	if (_save->getTile(_action.target) && _save->getTile(_action.target)->getMapData(MapData::O_OBJECT) && _save->getTile(_action.target)->getMapData(MapData::O_OBJECT)->getTUCost(MT_WALK) == 255)
	{
		return false;
	}

	originVoxel = Position(_origin.x*16 + 8, _origin.y*16 + 8, _origin.z*24);
	originVoxel.z += -_save->getTile(_origin)->getTerrainLevel();
	BattleUnit *bu = _save->getTile(_origin)->getUnit();
	originVoxel.z += bu->getHeight();
	originVoxel.z -= 3;
	if (originVoxel.z >= (_origin.z + 1)*24)
	{
		_origin.z++;
	}


	// determine the target voxel.
	// aim at the center of the floor
	targetVoxel = Position(_action.target.x*16 + 8, _action.target.y*16 + 8, _action.target.z*24 + 2);

	// we try 4 different curvatures to try and reach our goal.
	double curvature = 1.0;
	while (!foundCurve && curvature < 5.0)
	{
		_save->getTileEngine()->calculateParabola(originVoxel, targetVoxel, false, &_trajectory, bu, curvature, 1.0);
		if ((int)_trajectory.at(0).x/16 == (int)targetVoxel.x/16 && (int)_trajectory.at(0).y/16 == (int)targetVoxel.y/16)
		{
			foundCurve = true;
		}
		else
		{
			curvature += 1.0;
		}
		_trajectory.clear();
	}
	if (curvature == 5.0)
	{
		return false;
	}

	// apply some accuracy modifiers
	if (accuracy > 100)
		accuracy = 100;
	static const double maxDeviation = 0.08;
	static const double minDeviation = 0;
	double baseDeviation = (maxDeviation - (maxDeviation * accuracy / 100.0)) + minDeviation;
	double deviation = RNG::boxMuller(0, baseDeviation);

	_trajectory.clear();
	// finally do a line calculation and store this trajectory.
	_save->getTileEngine()->calculateParabola(originVoxel, targetVoxel, true, &_trajectory, bu, curvature, 1.0 + deviation);

	Position endPoint = _trajectory.at(_trajectory.size() - 1);
	endPoint.x /= 16;
	endPoint.y /= 16;
	endPoint.z /= 24;
	// check if the item would land on a tile with a blocking object, if so then we let it fly without deviation, it must land on a valid tile in that case
	if (_save->getTile(endPoint) && _save->getTile(endPoint)->getMapData(MapData::O_OBJECT) && _save->getTile(endPoint)->getMapData(MapData::O_OBJECT)->getTUCost(MT_WALK) == 255)
	{
		_trajectory.clear();
		// finally do a line calculation and store this trajectory.
		_save->getTileEngine()->calculateParabola(originVoxel, targetVoxel, true, &_trajectory, bu, curvature, 1.0);
	}


	return true;
}

void CCamera::CheckForMovement()
{	
	// Once we have the frame interval, we find the current speed
	float speed = (float)(kSpeed * g_FrameInterval);

	// Store the last position and view of the camera
	CVector3 vOldPosition = Position();
	CVector3 vOldView = View();

	// Use a flag to see if we movement backwards or not
	bool bMovedBack = false;


/////// * /////////// * /////////// * NEW * /////// * /////////// * /////////// *

	// Here is where we subtract the gravity acceleration from our velocity vector.
	// We then add that velocity vector to our camera to effect our camera (or player)
	// This is also how we handle the jump velocity when we hit space bar.
	// Notice that we multiply the gravity by the frame interval (dt).  This makes
	// it so faster video cards don't do a 2 frame jump, while TNT2 cards do 20 frames :)
	// This is necessary to make every computer use the same movement and jump speed.
	g_vVelocity.y -= (float)(kGravity * g_FrameInter