Index: ps/trunk/source/simulation2/components/ICmpObstruction.h =================================================================== --- ps/trunk/source/simulation2/components/ICmpObstruction.h (revision 7483) +++ ps/trunk/source/simulation2/components/ICmpObstruction.h (revision 7484) @@ -1,41 +1,46 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #ifndef INCLUDED_ICMPOBSTRUCTION #define INCLUDED_ICMPOBSTRUCTION #include "simulation2/system/Interface.h" -#include "simulation2/components/ICmpPosition.h" +#include "simulation2/components/ICmpObstructionManager.h" /** * Flags an entity as obstructing movement for other units, * and handles the processing of collision queries. */ class ICmpObstruction : public IComponent { public: + + virtual ICmpObstructionManager::tag_t GetObstruction() = 0; + + virtual entity_pos_t GetUnitRadius() = 0; + /** * Test whether this entity's footprint is colliding with any other's. * @return true if there is a collision */ virtual bool CheckCollisions() = 0; DECLARE_INTERFACE_TYPE(Obstruction) }; #endif // INCLUDED_ICMPOBSTRUCTION Index: ps/trunk/source/maths/Fixed.h =================================================================== --- ps/trunk/source/maths/Fixed.h (revision 7483) +++ ps/trunk/source/maths/Fixed.h (revision 7484) @@ -1,173 +1,184 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #ifndef INCLUDED_FIXED #define INCLUDED_FIXED #include "lib/types.h" #include "maths/Sqrt.h" template inline T round_away_from_zero(float value) { return (T)(value >= 0 ? value + 0.5f : value - 0.5f); } /** * A simple fixed-point number class, with no fancy features * like overflow checking or anything. (It has very few basic * features too, and needs to be substantially improved before * it'll be of much use.) * * Use CFixed_23_8 rather than using this class directly. */ template class CFixed { private: T value; explicit CFixed(T v) : value(v) { } public: enum { fract_bits = fract_bits_ }; CFixed() : value(0) { } static CFixed Zero() { return CFixed(0); } static CFixed Pi(); T GetInternalValue() const { return value; } void SetInternalValue(T n) { value = n; } // Conversion to/from primitive types: static CFixed FromInt(int n) { return CFixed(n << fract_bits); } static CFixed FromFloat(float n) { if (!isfinite(n)) return CFixed(0); float scaled = n * fract_pow2; return CFixed(round_away_from_zero(scaled)); } static CFixed FromDouble(double n) { if (!isfinite(n)) return CFixed(0); double scaled = n * fract_pow2; return CFixed(round_away_from_zero(scaled)); } float ToFloat() const { return value / (float)fract_pow2; } double ToDouble() const { return value / (double)fract_pow2; } int ToInt_RoundToZero() const { if (value > 0) return value >> fract_bits; else return (value + fract_pow2 - 1) >> fract_bits; } /// Returns true if the number is precisely 0. bool IsZero() const { return value == 0; } /// Equality. bool operator==(CFixed n) const { return (value == n.value); } /// Inequality. bool operator!=(CFixed n) const { return (value != n.value); } /// Numeric comparison. bool operator<=(CFixed n) const { return (value <= n.value); } /// Numeric comparison. bool operator<(CFixed n) const { return (value < n.value); } /// Numeric comparison. bool operator>=(CFixed n) const { return (value >= n.value); } /// Numeric comparison. bool operator>(CFixed n) const { return (value > n.value); } // Basic arithmetic: /// Add a CFixed. Might overflow. CFixed operator+(CFixed n) const { return CFixed(value + n.value); } /// Subtract a CFixed. Might overflow. CFixed operator-(CFixed n) const { return CFixed(value - n.value); } + /// Add a CFixed. Might overflow. + CFixed& operator+=(CFixed n) { value += n.value; return *this; } + + /// Subtract a CFixed. Might overflow. + CFixed& operator-=(CFixed n) { value -= n.value; return *this; } + /// Negate a CFixed. CFixed operator-() const { return CFixed(-value); } /// Divide by a CFixed. Must not have n.IsZero(). Might overflow. CFixed operator/(CFixed n) const { i64 t = (i64)value << fract_bits; return CFixed((T)(t / (i64)n.value)); } /// Multiply by an integer. Might overflow. CFixed operator*(int n) const { return CFixed(value * n); } /// Divide by an integer. Must not have n == 0. Cannot overflow. CFixed operator/(int n) const { return CFixed(value / n); } CFixed Absolute() const { return CFixed(abs(value)); } /** * Multiply by a CFixed. Likely to overflow if both numbers are large, * so we use an ugly name instead of operator* to make it obvious. */ CFixed Multiply(CFixed n) const { i64 t = (i64)value * (i64)n.value; return CFixed((T)(t >> fract_bits)); } CFixed Sqrt() const { if (value <= 0) return CFixed(0); u32 s = isqrt64(value); return CFixed((u64)s << (fract_bits / 2)); } + +private: + // Prevent dangerous accidental implicit conversions of floats to ints in certain operations + CFixed operator*(float n) const; + CFixed operator/(float n) const; }; /** * A fixed-point number class with 1-bit sign, 23-bit integral part, 8-bit fractional part. */ typedef CFixed CFixed_23_8; /** * Inaccurate approximation of atan2 over fixed-point numbers. * Maximum error is almost 0.08 radians (4.5 degrees). */ CFixed_23_8 atan2_approx(CFixed_23_8 y, CFixed_23_8 x); void sincos_approx(CFixed_23_8 a, CFixed_23_8& sin_out, CFixed_23_8& cos_out); #endif // INCLUDED_FIXED Index: ps/trunk/binaries/data/mods/_test.sim/simulation/templates/unitobstruct.xml =================================================================== --- ps/trunk/binaries/data/mods/_test.sim/simulation/templates/unitobstruct.xml (revision 7483) +++ ps/trunk/binaries/data/mods/_test.sim/simulation/templates/unitobstruct.xml (revision 7484) @@ -1,18 +1,20 @@ example 0 upright false 1.0 - + + + Index: ps/trunk/binaries/data/mods/public/simulation/components/TrainingQueue.js =================================================================== --- ps/trunk/binaries/data/mods/public/simulation/components/TrainingQueue.js (revision 7483) +++ ps/trunk/binaries/data/mods/public/simulation/components/TrainingQueue.js (revision 7484) @@ -1,217 +1,219 @@ var g_ProgressInterval = 1000; function TrainingQueue() {} TrainingQueue.prototype.Schema = "Allows the building to train new units." + "" + "" + "\n units/{civ}_support_female_citizen\n units/{civ}_support_trader\n units/celt_infantry_spearman_b\n " + "" + "" + "" + "" + ""; TrainingQueue.prototype.Init = function() { this.nextID = 1; this.queue = []; // Queue items are: // { // "id": 1, // "template": "units/example", // "count": 10, // "resources": { "wood": 100, ... }, // "timeTotal": 15000, // msecs // "timeRemaining": 10000, // msecs // } this.timer = undefined; // g_ProgressInterval msec timer, active while the queue is non-empty }; TrainingQueue.prototype.GetEntitiesList = function() { var string = this.template.Entities; // Replace the "{civ}" codes with this entity's civ ID var cmpIdentity = Engine.QueryInterface(this.entity, IID_Identity); if (cmpIdentity) string = string.replace(/\{civ\}/g, cmpIdentity.GetCiv()); return string.split(/\s+/); }; TrainingQueue.prototype.AddBatch = function(player, templateName, count) { // TODO: there should probably be a limit on the number of queued batches // TODO: there should be a way for the GUI to determine whether it's going // to be possible to add a batch (based on resource costs and length limits) // Find the template data so we can determine the build costs var cmpTempMan = Engine.QueryInterface(SYSTEM_ENTITY, IID_TemplateManager); var template = cmpTempMan.GetTemplate(templateName); if (!template) return; var timeMult = count; // TODO: we want some kind of discount for larger batches var costMult = count; var time = timeMult * (template.Cost.BuildTime || 1); var costs = {}; for each (var r in ["food", "wood", "stone", "metal"]) { if (template.Cost.Resources[r]) costs[r] = Math.floor(costMult * template.Cost.Resources[r]); else costs[r] = 0; } // Find the player var cmpPlayerMan = Engine.QueryInterface(SYSTEM_ENTITY, IID_PlayerManager); var playerEnt = cmpPlayerMan.GetPlayerByID(player); var cmpPlayer = Engine.QueryInterface(playerEnt, IID_Player); if (!cmpPlayer.TrySubtractResources(costs)) { // TODO: report error to player (they ran out of resources) return; } this.queue.push({ "id": this.nextID++, "template": templateName, "count": count, "resources": costs, "timeTotal": time*1000, "timeRemaining": time*1000, }); // If this is the first item in the queue, start the timer if (!this.timer) { var cmpTimer = Engine.QueryInterface(SYSTEM_ENTITY, IID_Timer); this.timer = cmpTimer.SetTimeout(this.entity, IID_TrainingQueue, "ProgressTimeout", g_ProgressInterval, {}); } }; TrainingQueue.prototype.RemoveBatch = function(player, id) { for (var i = 0; i < this.queue.length; ++i) { var item = this.queue[i]; if (item.id != id) continue; // Now we've found the item to remove // Find the player var cmpPlayerMan = Engine.QueryInterface(SYSTEM_ENTITY, IID_PlayerManager); var playerEnt = cmpPlayerMan.GetPlayerByID(player); var cmpPlayer = Engine.QueryInterface(playerEnt, IID_Player); // Refund the resource cost for this batch cmpPlayer.AddResources(item.resources); // Remove from the queue // (We don't need to remove the timer - it'll expire if it discovers the queue is empty) this.queue.splice(i, 1); return; } } TrainingQueue.prototype.GetQueue = function() { var out = []; for each (var item in this.queue) { out.push({ "id": item.id, "template": item.template, "count": item.count, "progress": 1-(item.timeRemaining/item.timeTotal), }); } return out; }; TrainingQueue.prototype.OnDestroy = function() { // If the building is destroyed while it's got a large training queue, // you lose all the resources invested in that queue. That'll teach you // to be so reckless with your buildings. if (this.timer) { var cmpTimer = Engine.QueryInterface(SYSTEM_ENTITY, IID_Timer); cmpTimer.CancelTimer(this.timer); } }; TrainingQueue.prototype.SpawnUnits = function(templateName, count) { var cmpFootprint = Engine.QueryInterface(this.entity, IID_Footprint); var cmpPosition = Engine.QueryInterface(this.entity, IID_Position); var cmpOwnership = Engine.QueryInterface(this.entity, IID_Ownership); for (var i = 0; i < count; ++i) { var ent = Engine.AddEntity(templateName); var pos = cmpFootprint.PickSpawnPoint(ent); if (pos.y < 0) { // Whoops, something went wrong (maybe there wasn't any space to spawn the unit). // What should we do here? // For now, just move the unit into the middle of the building where it'll probably get stuck pos = cmpPosition.GetPosition(); } var cmpNewPosition = Engine.QueryInterface(ent, IID_Position); cmpNewPosition.JumpTo(pos.x, pos.z); // TODO: what direction should they face in? var cmpNewOwnership = Engine.QueryInterface(ent, IID_Ownership); cmpNewOwnership.SetOwner(cmpOwnership.GetOwner()); // TODO: move to rally points } }; TrainingQueue.prototype.ProgressTimeout = function(data) { // Allocate the 1000msecs to as many queue items as it takes // until we've used up all the time (so that we work accurately // with items that take fractions of a second) var time = g_ProgressInterval; + time *= 10; // XXX: this is a hack to make testing easier + while (time > 0 && this.queue.length) { var item = this.queue[0]; if (item.timeRemaining > time) { item.timeRemaining -= time; break; } // This item is finished now time -= item.timeRemaining; this.SpawnUnits(item.template, item.count); this.queue.shift(); } // If the queue's empty, delete the timer, else repeat it if (this.queue.length == 0) { this.timer = undefined; } else { var cmpTimer = Engine.QueryInterface(SYSTEM_ENTITY, IID_Timer); this.timer = cmpTimer.SetTimeout(this.entity, IID_TrainingQueue, "ProgressTimeout", g_ProgressInterval, data); } } Engine.RegisterComponentType(IID_TrainingQueue, "TrainingQueue", TrainingQueue); Index: ps/trunk/binaries/data/mods/public/simulation/templates/template_structure_defense_scout_tower.xml =================================================================== --- ps/trunk/binaries/data/mods/public/simulation/templates/template_structure_defense_scout_tower.xml (revision 7483) +++ ps/trunk/binaries/data/mods/public/simulation/templates/template_structure_defense_scout_tower.xml (revision 7484) @@ -1,29 +1,32 @@ Outpost 53 24 50 50 1200 15.0 40.0 10.0 structures/fndn_2x2.xml 8.0 + + + Index: ps/trunk/binaries/data/mods/public/simulation/templates/template_structure_gaia_settlement.xml =================================================================== --- ps/trunk/binaries/data/mods/public/simulation/templates/template_structure_gaia_settlement.xml (revision 7483) +++ ps/trunk/binaries/data/mods/public/simulation/templates/template_structure_gaia_settlement.xml (revision 7484) @@ -1,17 +1,20 @@ gaia Settlement Settlement PortraitSheetSpecial 1 settlement 8.0 + + + Index: ps/trunk/source/ps/Profile.cpp =================================================================== --- ps/trunk/source/ps/Profile.cpp (revision 7483) +++ ps/trunk/source/ps/Profile.cpp (revision 7484) @@ -1,673 +1,673 @@ /* Copyright (C) 2009 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ /* * GPG3-style hierarchical profiler */ #include "precompiled.h" #include "Profile.h" #include "ProfileViewer.h" #include "lib/timer.h" #if OS_WIN #include "lib/sysdep/os/win/wdbg_heap.h" #endif #if defined(__GLIBC__) && !defined(NDEBUG) //# define USE_GLIBC_MALLOC_HOOK # define USE_GLIBC_MALLOC_OVERRIDE # include # include "lib/sysdep/cpu.h" #endif /////////////////////////////////////////////////////////////////////////////////////////////// // CProfileNodeTable /** * Class CProfileNodeTable: Implement ProfileViewer's AbstractProfileTable * interface in order to display profiling data in-game. */ class CProfileNodeTable : public AbstractProfileTable { public: CProfileNodeTable(CProfileNode* n); virtual ~CProfileNodeTable(); // Implementation of AbstractProfileTable interface virtual CStr GetName(); virtual CStr GetTitle(); virtual size_t GetNumberRows(); virtual const std::vector& GetColumns(); virtual CStr GetCellText(size_t row, size_t col); virtual AbstractProfileTable* GetChild(size_t row); virtual bool IsHighlightRow(size_t row); private: /** * struct ColumnDescription: The only purpose of this helper structure * is to provide the global constructor that sets up the column * description. */ struct ColumnDescription { std::vector columns; ColumnDescription() { columns.push_back(ProfileColumn("Name", 230)); columns.push_back(ProfileColumn("calls/frame", 100)); columns.push_back(ProfileColumn("msec/frame", 100)); columns.push_back(ProfileColumn("%/frame", 100)); columns.push_back(ProfileColumn("%/parent", 100)); columns.push_back(ProfileColumn("mem allocs", 100)); } }; /// The node represented by this table CProfileNode* node; /// Columns description (shared by all instances) static ColumnDescription columnDescription; }; CProfileNodeTable::ColumnDescription CProfileNodeTable::columnDescription; // Constructor/Destructor CProfileNodeTable::CProfileNodeTable(CProfileNode* n) { node = n; } CProfileNodeTable::~CProfileNodeTable() { } // Short name (= name of profile node) CStr CProfileNodeTable::GetName() { return node->GetName(); } // Title (= explanatory text plus time totals) CStr CProfileNodeTable::GetTitle() { char buf[512]; sprintf_s(buf, ARRAY_SIZE(buf), "Profiling Information for: %s (Time in node: %.3f msec/frame)", node->GetName(), node->GetFrameTime() * 1000.0f ); return buf; } // Total number of children size_t CProfileNodeTable::GetNumberRows() { return node->GetChildren()->size() + node->GetScriptChildren()->size() + 1; } // Column description const std::vector& CProfileNodeTable::GetColumns() { return columnDescription.columns; } // Retrieve cell text CStr CProfileNodeTable::GetCellText(size_t row, size_t col) { CProfileNode* child; size_t nrchildren = node->GetChildren()->size(); size_t nrscriptchildren = node->GetScriptChildren()->size(); char buf[256] = "?"; if (row < nrchildren) child = (*node->GetChildren())[row]; else if (row < nrchildren + nrscriptchildren) child = (*node->GetScriptChildren())[row - nrchildren]; else if (row > nrchildren + nrscriptchildren) return "!bad row!"; else { // "unlogged" row if (col == 0) return "unlogged"; else if (col == 1) return ""; float unlogged = node->GetFrameTime(); long unlogged_mallocs = node->GetFrameMallocs(); CProfileNode::const_profile_iterator it; for (it = node->GetChildren()->begin(); it != node->GetChildren()->end(); ++it) { unlogged -= (*it)->GetFrameTime(); unlogged_mallocs -= (*it)->GetFrameMallocs(); } for (it = node->GetScriptChildren()->begin(); it != node->GetScriptChildren()->end(); ++it) { unlogged -= (*it)->GetFrameTime(); unlogged_mallocs -= (*it)->GetFrameMallocs(); } if (col == 2) - sprintf_s(buf, sizeof(buf), "%.3f", unlogged * 1000.0f); + sprintf_s(buf, ARRAY_SIZE(buf), "%.3f", unlogged * 1000.0f); else if (col == 3) - sprintf_s(buf, sizeof(buf), "%.1f", unlogged / g_Profiler.GetRoot()->GetFrameTime()); + sprintf_s(buf, ARRAY_SIZE(buf), "%.1f", unlogged / g_Profiler.GetRoot()->GetFrameTime()); else if (col == 4) - sprintf_s(buf, sizeof(buf), "%.1f", unlogged * 100.0f / g_Profiler.GetRoot()->GetFrameTime()); + sprintf_s(buf, ARRAY_SIZE(buf), "%.1f", unlogged * 100.0f / g_Profiler.GetRoot()->GetFrameTime()); else if (col == 5) - sprintf_s(buf, sizeof(buf), "%ld", unlogged_mallocs); + sprintf_s(buf, ARRAY_SIZE(buf), "%ld", unlogged_mallocs); return CStr(buf); } switch(col) { default: case 0: return child->GetName(); case 1: #ifdef PROFILE_AMORTIZE sprintf_s(buf, ARRAY_SIZE(buf), "%.3f", child->GetFrameCalls()); #else - sprintf_s(buf, sizeof(buf), "%d", child->GetFrameCalls()); + sprintf_s(buf, ARRAY_SIZE(buf), "%d", child->GetFrameCalls()); #endif break; case 2: sprintf_s(buf, ARRAY_SIZE(buf), "%.3f", child->GetFrameTime() * 1000.0f); break; case 3: sprintf_s(buf, ARRAY_SIZE(buf), "%.1f", child->GetFrameTime() * 100.0 / g_Profiler.GetRoot()->GetFrameTime()); break; case 4: sprintf_s(buf, ARRAY_SIZE(buf), "%.1f", child->GetFrameTime() * 100.0 / node->GetFrameTime()); break; case 5: sprintf_s(buf, ARRAY_SIZE(buf), "%ld", child->GetFrameMallocs()); break; } return CStr(buf); } // Return a pointer to the child table if the child node is expandable AbstractProfileTable* CProfileNodeTable::GetChild(size_t row) { CProfileNode* child; size_t nrchildren = node->GetChildren()->size(); size_t nrscriptchildren = node->GetScriptChildren()->size(); if (row < nrchildren) child = (*node->GetChildren())[row]; else if (row < nrchildren + nrscriptchildren) child = (*node->GetScriptChildren())[row - nrchildren]; else return 0; if (child->CanExpand()) return child->display_table; return 0; } // Highlight all script nodes bool CProfileNodeTable::IsHighlightRow(size_t row) { size_t nrchildren = node->GetChildren()->size(); size_t nrscriptchildren = node->GetScriptChildren()->size(); return (row >= nrchildren && row < (nrchildren + nrscriptchildren)); } /////////////////////////////////////////////////////////////////////////////////////////////// // CProfileNode implementation // Note: As with the GPG profiler, name is assumed to be a pointer to a constant string; only pointer equality is checked. CProfileNode::CProfileNode( const char* _name, CProfileNode* _parent ) { name = _name; recursion = 0; Reset(); parent = _parent; display_table = new CProfileNodeTable(this); Reset(); } CProfileNode::~CProfileNode() { profile_iterator it; for( it = children.begin(); it != children.end(); it++ ) delete( *it ); for( it = script_children.begin(); it != script_children.end(); it++ ) delete( *it ); delete display_table; } const CProfileNode* CProfileNode::GetChild( const char* childName ) const { const_profile_iterator it; for( it = children.begin(); it != children.end(); it++ ) if( (*it)->name == childName ) return( *it ); return( NULL ); } const CProfileNode* CProfileNode::GetScriptChild( const char* childName ) const { const_profile_iterator it; for( it = script_children.begin(); it != script_children.end(); it++ ) if( (*it)->name == childName ) return( *it ); return( NULL ); } CProfileNode* CProfileNode::GetChild( const char* childName ) { profile_iterator it; for( it = children.begin(); it != children.end(); it++ ) if( (*it)->name == childName ) return( *it ); CProfileNode* newNode = new CProfileNode( childName, this ); children.push_back( newNode ); return( newNode ); } CProfileNode* CProfileNode::GetScriptChild( const char* childName ) { profile_iterator it; for( it = script_children.begin(); it != script_children.end(); it++ ) if( (*it)->name == childName ) return( *it ); CProfileNode* newNode = new CProfileNode( childName, this ); script_children.push_back( newNode ); return( newNode ); } bool CProfileNode::CanExpand() { return( !( children.empty() && script_children.empty() ) ); } void CProfileNode::Reset() { calls_total = 0; calls_frame_current = 0; #ifdef PROFILE_AMORTIZE int i; for( i = 0; i < PROFILE_AMORTIZE_FRAMES; i++ ) { calls_frame_buffer[i] = 0; time_frame_buffer[i] = 0.0; } calls_frame_last = calls_frame_buffer; calls_frame_amortized = 0.0f; #else calls_frame_last = 0; #endif time_total = 0.0; time_frame_current = 0.0; #ifdef PROFILE_AMORTIZE time_frame_last = time_frame_buffer; time_frame_amortized = 0.0; #else time_frame_last = 0.0; #endif mallocs_total = 0; mallocs_frame_current = 0; mallocs_frame_last = 0; profile_iterator it; for( it = children.begin(); it != children.end(); it++ ) (*it)->Reset(); for( it = script_children.begin(); it != script_children.end(); it++ ) (*it)->Reset(); } void CProfileNode::Frame() { calls_total += calls_frame_current; time_total += time_frame_current; mallocs_total += mallocs_frame_current; #ifdef PROFILE_AMORTIZE calls_frame_amortized -= *calls_frame_last; *calls_frame_last = calls_frame_current; calls_frame_amortized += calls_frame_current; time_frame_amortized -= *time_frame_last; *time_frame_last = time_frame_current; time_frame_amortized += time_frame_current; if( ++calls_frame_last == ( calls_frame_buffer + PROFILE_AMORTIZE_FRAMES ) ) calls_frame_last = calls_frame_buffer; if( ++time_frame_last == ( time_frame_buffer + PROFILE_AMORTIZE_FRAMES ) ) time_frame_last = time_frame_buffer; #else calls_frame_last = calls_frame_current; time_frame_last = time_frame_current; #endif mallocs_frame_last = mallocs_frame_current; calls_frame_current = 0; time_frame_current = 0.0; mallocs_frame_current = 0; profile_iterator it; for( it = children.begin(); it != children.end(); it++ ) (*it)->Frame(); for( it = script_children.begin(); it != script_children.end(); it++ ) (*it)->Frame(); } // TODO: these should probably only count allocations that occur in the thread being profiled #if OS_WIN static void alloc_hook_initialize() { } static long get_memory_alloc_count() { return (long)wdbg_heap_NumberOfAllocations(); } #elif defined(USE_GLIBC_MALLOC_HOOK) // Set up malloc hooks to count allocations - see // http://www.gnu.org/software/libc/manual/html_node/Hooks-for-Malloc.html static intptr_t malloc_count = 0; static void *(*old_malloc_hook) (size_t, const void*); static pthread_mutex_t alloc_hook_mutex = PTHREAD_MUTEX_INITIALIZER; static void *malloc_hook(size_t size, const void* UNUSED(caller)) { // This doesn't really work across threads. The hooks are global variables, and // we have to temporarily unhook in order to call the real malloc, and during that // time period another thread may perform an unhooked (hence uncounted) allocation // which we will miss. // Two threads may execute the hook simultaneously, so we need to do the // temporary unhooking in a thread-safe way, so for simplicity we just use a mutex. pthread_mutex_lock(&alloc_hook_mutex); ++malloc_count; __malloc_hook = old_malloc_hook; void* result = malloc(size); old_malloc_hook = __malloc_hook; __malloc_hook = malloc_hook; pthread_mutex_unlock(&alloc_hook_mutex); return result; } static void alloc_hook_initialize() { pthread_mutex_lock(&alloc_hook_mutex); old_malloc_hook = __malloc_hook; __malloc_hook = malloc_hook; // (we don't want to bother hooking realloc and memalign, because if they allocate // new memory then they'll be caught by the malloc hook anyway) pthread_mutex_unlock(&alloc_hook_mutex); } /* It would be nice to do: __attribute__ ((visibility ("default"))) void (*__malloc_initialize_hook)() = malloc_initialize_hook; except that doesn't seem to work in practice, since something (?) resets the hook to NULL some time while loading the game, after we've set it here - so we just call malloc_initialize_hook once inside CProfileManager::Frame instead and hope nobody deletes our hook after that. */ static long get_memory_alloc_count() { return malloc_count; } #elif defined(USE_GLIBC_MALLOC_OVERRIDE) static intptr_t alloc_count = 0; // We override the malloc/realloc/calloc/free functions and then use dlsym to // defer the actual allocation to the real libc implementation. // The dlsym call will (in glibc 2.9/2.10) call calloc once (to allocate an error // message structure), so we have a bootstrapping problem when trying to // get the first called function via dlsym. So we kludge it by returning a statically-allocated // buffer for the very first call to calloc after we've called dlsym. // This is quite hacky but it seems to just about work in practice... static bool alloc_bootstrapped = false; static char alloc_bootstrap_buffer[32]; // sufficient for x86_64 static bool alloc_has_called_dlsym = false; // (We'll only be running a single thread at this point so no need for locking these variables) //#define ALLOC_DEBUG void* malloc(size_t sz) { cpu_AtomicAdd(&alloc_count, 1); static void *(*libc_malloc)(size_t); if (libc_malloc == NULL) { alloc_has_called_dlsym = true; libc_malloc = (void *(*)(size_t)) dlsym(RTLD_NEXT, "malloc"); } void* ret = libc_malloc(sz); #ifdef ALLOC_DEBUG printf("### malloc(%d) = %p\n", sz, ret); #endif return ret; } void* realloc(void* ptr, size_t sz) { cpu_AtomicAdd(&alloc_count, 1); static void *(*libc_realloc)(void*, size_t); if (libc_realloc == NULL) { alloc_has_called_dlsym = true; libc_realloc = (void *(*)(void*, size_t)) dlsym(RTLD_NEXT, "realloc"); } void* ret = libc_realloc(ptr, sz); #ifdef ALLOC_DEBUG printf("### realloc(%p, %d) = %p\n", ptr, sz, ret); #endif return ret; } void* calloc(size_t nm, size_t sz) { cpu_AtomicAdd(&alloc_count, 1); static void *(*libc_calloc)(size_t, size_t); if (libc_calloc == NULL) { if (alloc_has_called_dlsym && !alloc_bootstrapped) { debug_assert(nm*sz <= ARRAY_SIZE(alloc_bootstrap_buffer)); #ifdef ALLOC_DEBUG printf("### calloc-bs(%d, %d) = %p\n", nm, sz, alloc_bootstrap_buffer); #endif alloc_bootstrapped = true; return alloc_bootstrap_buffer; } alloc_has_called_dlsym = true; libc_calloc = (void *(*)(size_t, size_t)) dlsym(RTLD_NEXT, "calloc"); } void* ret = libc_calloc(nm, sz); #ifdef ALLOC_DEBUG printf("### calloc(%d, %d) = %p\n", nm, sz, ret); #endif return ret; } void free(void* ptr) { static void (*libc_free)(void*); if (libc_free == NULL) { alloc_has_called_dlsym = true; libc_free = (void (*)(void*)) dlsym(RTLD_NEXT, "free"); } libc_free(ptr); #ifdef ALLOC_DEBUG printf("### free(%p)\n", ptr); #endif } static void alloc_hook_initialize() { } static long get_memory_alloc_count() { return alloc_count; } #else static void alloc_hook_initialize() { } static long get_memory_alloc_count() { // TODO: don't show this column of data when we don't have sensible values // to display. return 0; } #endif void CProfileNode::Call() { calls_frame_current++; if( recursion++ == 0 ) { start = timer_Time(); start_mallocs = get_memory_alloc_count(); } } bool CProfileNode::Return() { if( !parent ) return( false ); if( ( --recursion == 0 ) && ( calls_frame_current != 0 ) ) { time_frame_current += ( timer_Time() - start ); mallocs_frame_current += ( get_memory_alloc_count() - start_mallocs ); } return( recursion == 0 ); } void CProfileNode::ScriptingInit() { AddProperty( L"name", (IJSObject::GetFn)&CProfileNode::JS_GetName ); /* AddReadOnlyClassProperty( L"callsTotal", &CProfileNode::calls_total ); AddReadOnlyClassProperty( L"callsPerFrame", &CProfileNode::calls_frame_last ); AddReadOnlyClassProperty( L"timeTotal", &CProfileNode::time_total ); AddReadOnlyClassProperty( L"timePerFrame", &CProfileNode::time_frame_last ); */ CJSObject::ScriptingInit( "ProfilerNode" ); } CProfileManager::CProfileManager() { root = new CProfileNode( "root", NULL ); current = root; frame_start = 0.0; frame_start_mallocs = 0; g_ProfileViewer.AddRootTable(root->display_table); } CProfileManager::~CProfileManager() { std::map::iterator it; for( it = m_internedStrings.begin(); it != m_internedStrings.end(); it++ ) delete[]( it->second ); delete( root ); } void CProfileManager::Start( const char* name ) { if( name != current->GetName() ) current = current->GetChild( name ); current->Call(); } void CProfileManager::StartScript( const char* name ) { if( name != current->GetName() ) current = current->GetScriptChild( name ); current->Call(); } const char* CProfileManager::InternString( const CStr8& intern ) { std::map::iterator it = m_internedStrings.find( intern ); if( it != m_internedStrings.end() ) return( it->second ); size_t length = intern.length(); char* data = new char[length + 1]; strcpy( data, intern.c_str() ); data[length] = 0; m_internedStrings.insert( std::pair( intern, data ) ); return( data ); } void CProfileManager::Stop() { if( current->Return() ) current = current->GetParent(); } void CProfileManager::Reset() { root->Reset(); start = frame_start = timer_Time(); start_mallocs = frame_start_mallocs = get_memory_alloc_count(); } void CProfileManager::Frame() { ONCE(alloc_hook_initialize()); root->time_frame_current = ( timer_Time() - frame_start ); root->mallocs_frame_current = ( get_memory_alloc_count() - frame_start_mallocs ); root->Frame(); frame_start = timer_Time(); frame_start_mallocs = get_memory_alloc_count(); } void CProfileManager::StructuralReset() { delete( root ); root = new CProfileNode( "root", NULL ); current = root; g_ProfileViewer.AddRootTable(root->display_table); } Index: ps/trunk/source/gui/MiniMap.cpp =================================================================== --- ps/trunk/source/gui/MiniMap.cpp (revision 7483) +++ ps/trunk/source/gui/MiniMap.cpp (revision 7484) @@ -1,636 +1,637 @@ /* Copyright (C) 2009 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #include "precompiled.h" #include #include "MiniMap.h" #include "graphics/GameView.h" #include "graphics/MiniPatch.h" #include "graphics/Terrain.h" #include "graphics/TextureEntry.h" #include "graphics/TextureManager.h" #include "graphics/Unit.h" #include "graphics/UnitManager.h" #include "lib/ogl.h" #include "lib/external_libraries/sdl.h" #include "lib/bits.h" #include "lib/timer.h" +#include "lib/sysdep/cpu.h" #include "network/NetMessage.h" #include "ps/Game.h" #include "ps/Interact.h" #include "ps/Player.h" #include "ps/Profile.h" #include "ps/World.h" #include "renderer/Renderer.h" #include "renderer/WaterManager.h" #include "scripting/GameEvents.h" #include "simulation/Entity.h" #include "simulation/EntityTemplate.h" #include "simulation/LOSManager.h" #include "simulation/TerritoryManager.h" #include "simulation2/Simulation2.h" #include "simulation2/components/ICmpMinimap.h" bool g_TerrainModified = false; bool g_GameRestarted = false; // used by GetMapSpaceCoords (precalculated as an optimization). // this was formerly access via inline asm, which required it to be // static data instead of a class member. that is no longer the case, // but we leave it because this is slightly more efficient. static float m_scaleX, m_scaleY; static unsigned int ScaleColor(unsigned int color, float x) { unsigned int r = unsigned(float(color & 0xff) * x); unsigned int g = unsigned(float((color>>8) & 0xff) * x); unsigned int b = unsigned(float((color>>16) & 0xff) * x); return (0xff000000 | r | g<<8 | b<<16); } CMiniMap::CMiniMap() : m_TerrainTexture(0), m_TerrainData(0), m_MapSize(0), m_Terrain(0), m_LOSTexture(0), m_LOSData(0), m_UnitManager(0) { AddSetting(GUIST_CColor, "fov_wedge_color"); AddSetting(GUIST_CStr, "tooltip"); AddSetting(GUIST_CStr, "tooltip_style"); m_Clicking = false; } CMiniMap::~CMiniMap() { Destroy(); } void CMiniMap::HandleMessage(const SGUIMessage &Message) { switch(Message.type) { case GUIM_MOUSE_PRESS_LEFT: { SetCameraPos(); m_Clicking = true; break; } case GUIM_MOUSE_RELEASE_LEFT: { if(m_Clicking) SetCameraPos(); m_Clicking = false; break; } case GUIM_MOUSE_DBLCLICK_LEFT: { if(m_Clicking) SetCameraPos(); m_Clicking = false; break; } case GUIM_MOUSE_ENTER: { g_Selection.m_mouseOverMM = true; break; } case GUIM_MOUSE_LEAVE: { g_Selection.m_mouseOverMM = false; m_Clicking = false; break; } case GUIM_MOUSE_RELEASE_RIGHT: { CMiniMap::FireWorldClickEvent(SDL_BUTTON_RIGHT, 1); break; } case GUIM_MOUSE_DBLCLICK_RIGHT: { CMiniMap::FireWorldClickEvent(SDL_BUTTON_RIGHT, 2); break; } case GUIM_MOUSE_MOTION: { if (m_Clicking) SetCameraPos(); break; } default: break; } // switch } void CMiniMap::SetCameraPos() { CTerrain *MMTerrain=g_Game->GetWorld()->GetTerrain(); CVector3D CamOrient=m_Camera->m_Orientation.GetTranslation(); //get center point of screen int x = g_Renderer.GetWidth()/2; int y = g_Renderer.GetHeight()/2; CVector3D ScreenMiddle=m_Camera->GetWorldCoordinates(x,y); //Get Vector required to go from camera position to ScreenMiddle CVector3D TransVector; TransVector.X=CamOrient.X-ScreenMiddle.X; TransVector.Z=CamOrient.Z-ScreenMiddle.Z; //world position of where mouse clicked CVector3D Destination; CPos MousePos = GetMousePos(); //X and Z according to proportion of mouse position and minimap Destination.X = CELL_SIZE * m_MapSize * ( (MousePos.x - m_CachedActualSize.left) / m_CachedActualSize.GetWidth() ); Destination.Z = CELL_SIZE * m_MapSize * ( (m_CachedActualSize.bottom - MousePos.y) / m_CachedActualSize.GetHeight() ); m_Camera->m_Orientation._14=Destination.X; m_Camera->m_Orientation._34=Destination.Z; m_Camera->m_Orientation._14+=TransVector.X; m_Camera->m_Orientation._34+=TransVector.Z; //Lock Y coord. No risk of zoom exceeding limit-Y does not increase float Height=MMTerrain->GetExactGroundLevel( m_Camera->m_Orientation._14, m_Camera->m_Orientation._34) + g_YMinOffset; if (m_Camera->m_Orientation._24 < Height) { m_Camera->m_Orientation._24=Height; } m_Camera->UpdateFrustum(); } void CMiniMap::FireWorldClickEvent(int button, int clicks) { //debug_printf(L"FireWorldClickEvent: button %d, clicks %d\n", button, clicks); CPos MousePos = GetMousePos(); CVector2D Destination; //X and Z according to proportion of mouse position and minimap Destination.x = CELL_SIZE * m_MapSize * ( (MousePos.x - m_CachedActualSize.left) / m_CachedActualSize.GetWidth() ); Destination.y = CELL_SIZE * m_MapSize * ( (m_CachedActualSize.bottom - MousePos.y) / m_CachedActualSize.GetHeight() ); g_JSGameEvents.FireWorldClick( button, clicks, NMT_GOTO, -1, NMT_RUN, -1, NULL, (int)Destination.x, (int)Destination.y); } // render view rect : John M. Mena // This sets up and draws the rectangle on the mini-map // which represents the view of the camera in the world. void CMiniMap::DrawViewRect() { // Get correct world coordinates based off corner of screen start // at Bottom Left and going CW CVector3D hitPt[4]; hitPt[0]=m_Camera->GetWorldCoordinates(0,g_Renderer.GetHeight()); hitPt[1]=m_Camera->GetWorldCoordinates(g_Renderer.GetWidth(),g_Renderer.GetHeight()); hitPt[2]=m_Camera->GetWorldCoordinates(g_Renderer.GetWidth(),0); hitPt[3]=m_Camera->GetWorldCoordinates(0,0); float ViewRect[4][2]; for (int i=0;i<4;i++) { // convert to minimap space float px=hitPt[i].X; float pz=hitPt[i].Z; ViewRect[i][0]=(m_CachedActualSize.GetWidth()*px/float(CELL_SIZE*m_MapSize)); ViewRect[i][1]=(m_CachedActualSize.GetHeight()*pz/float(CELL_SIZE*m_MapSize)); } // Enable Scissoring as to restrict the rectangle // to only the mini-map below by retrieving the mini-maps // screen coords. glScissor((int)m_CachedActualSize.left, 0, (int)m_CachedActualSize.right, (int)m_CachedActualSize.GetHeight()); glEnable(GL_SCISSOR_TEST); glEnable(GL_LINE_SMOOTH); glLineWidth(2.0f); glColor3f(1.0f, 0.3f, 0.3f); // Draw the viewing rectangle with the ScEd's conversion algorithm const float x = m_CachedActualSize.left, y = m_CachedActualSize.bottom; glBegin(GL_LINE_LOOP); glVertex2f(x+ViewRect[0][0], y-ViewRect[0][1]); glVertex2f(x+ViewRect[1][0], y-ViewRect[1][1]); glVertex2f(x+ViewRect[2][0], y-ViewRect[2][1]); glVertex2f(x+ViewRect[3][0], y-ViewRect[3][1]); glEnd(); // restore state glDisable(GL_SCISSOR_TEST); glDisable(GL_LINE_SMOOTH); glLineWidth(1.0f); } struct MinimapUnitVertex { u8 r, g, b, a; float x, y; }; void CMiniMap::Draw() { PROFILE("minimap"); // The terrain isn't actually initialized until the map is loaded, which // happens when the game is started, so abort until then. if(!(GetGUI() && g_Game && g_Game->IsGameStarted())) return; glDisable(GL_DEPTH_TEST); // Set our globals in case they hadn't been set before m_Camera = g_Game->GetView()->GetCamera(); m_Terrain = g_Game->GetWorld()->GetTerrain(); m_UnitManager = &g_Game->GetWorld()->GetUnitManager(); m_Width = (u32)(m_CachedActualSize.right - m_CachedActualSize.left); m_Height = (u32)(m_CachedActualSize.bottom - m_CachedActualSize.top); m_MapSize = m_Terrain->GetVerticesPerSide(); m_TextureSize = (GLsizei)round_up_to_pow2((size_t)m_MapSize); m_scaleX = float(m_Width) / float(m_MapSize - 1); m_scaleY = float(m_Height) / float(m_MapSize - 1); if(!m_TerrainTexture || g_GameRestarted) CreateTextures(); // do not limit this as with LOS updates below - we must update // immediately after changes are reported because this flag will be // reset at the end of the frame. if(g_TerrainModified) RebuildTerrainTexture(); // only update 10x / second // (note: since units only move a few pixels per second on the minimap, // we can get away with infrequent updates; this is slow, ~20ms) static double last_time; const double cur_time = timer_Time(); if(cur_time - last_time > 100e-3) // 10 updates/sec { last_time = cur_time; CLOSManager* losMgr = g_Game->GetWorld()->GetLOSManager(); if(losMgr->m_LOSSetting != LOS_SETTING_ALL_VISIBLE) RebuildLOSTexture(); } const float texCoordMax = ((float)m_MapSize - 1) / ((float)m_TextureSize); const float x = m_CachedActualSize.left, y = m_CachedActualSize.bottom; const float x2 = m_CachedActualSize.right, y2 = m_CachedActualSize.top; const float z = GetBufferedZ(); // Draw the main textured quad g_Renderer.BindTexture(0, m_TerrainTexture); glTexEnvf(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_REPLACE); glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR); glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR); glBegin(GL_QUADS); glTexCoord2f(0.0f, 0.0f); glVertex3f(x, y, z); glTexCoord2f(texCoordMax, 0.0f); glVertex3f(x2, y, z); glTexCoord2f(texCoordMax, texCoordMax); glVertex3f(x2, y2, z); glTexCoord2f(0.0f, texCoordMax); glVertex3f(x, y2, z); glEnd(); // Shade territories by player CTerritoryManager* territoryMgr = g_Game->GetWorld()->GetTerritoryManager(); std::vector& territories = territoryMgr->GetTerritories(); PROFILE_START("minimap territory shade"); glDisable(GL_TEXTURE_2D); glEnable(GL_BLEND); glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA); for( size_t i=0; iowner->GetPlayerID() == 0 ) continue; std::vector& boundary = territories[i]->boundary; SPlayerColour col = territories[i]->owner->GetColour(); glColor4f(col.r, col.g, col.b, 0.25f); glBegin(GL_POLYGON); for( size_t j=0; jGetTilesPerSide() * CELL_SIZE); float fy = boundary[j].y / (m_Terrain->GetTilesPerSide() * CELL_SIZE); glVertex3f( x*(1-fx) + x2*fx, y*(1-fy) + y2*fy, z ); } glEnd(); } glDisable(GL_BLEND); PROFILE_END("minimap territory shade"); // Draw territory boundaries glEnable(GL_LINE_SMOOTH); glLineWidth(1.0f); glEnable(GL_BLEND); glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA); glColor4f(0.8f, 0.8f, 0.8f, 0.8f); for( size_t i=0; i& boundary = territories[i]->boundary; glBegin(GL_LINE_LOOP); for( size_t j=0; jGetTilesPerSide() * CELL_SIZE); float fy = boundary[j].y / (m_Terrain->GetTilesPerSide() * CELL_SIZE); glVertex3f( x*(1-fx) + x2*fx, y*(1-fy) + y2*fy, z ); } glEnd(); } glLineWidth(1.0f); glDisable(GL_LINE_SMOOTH); glDisable(GL_BLEND); // Draw the LOS quad in black, using alpha values from the LOS texture g_Renderer.BindTexture(0, m_LOSTexture); glTexEnvi(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_COMBINE); glTexEnvi(GL_TEXTURE_ENV, GL_COMBINE_RGB_ARB, GL_REPLACE); glTexEnvi(GL_TEXTURE_ENV, GL_SOURCE0_RGB_ARB, GL_PRIMARY_COLOR_ARB); glTexEnvi(GL_TEXTURE_ENV, GL_OPERAND0_RGB_ARB, GL_SRC_COLOR); glTexEnvi(GL_TEXTURE_ENV, GL_COMBINE_ALPHA_ARB, GL_REPLACE); glTexEnvi(GL_TEXTURE_ENV, GL_SOURCE0_ALPHA_ARB, GL_TEXTURE); glTexEnvi(GL_TEXTURE_ENV, GL_OPERAND0_ALPHA_ARB, GL_SRC_ALPHA); glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR); glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR); glEnable(GL_BLEND); glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA); glBegin(GL_QUADS); glColor3f(0.0f, 0.0f, 0.0f); glTexCoord2f(0.0f, 0.0f); glVertex3f(x, y, z); glTexCoord2f(texCoordMax, 0.0f); glVertex3f(x2, y, z); glTexCoord2f(texCoordMax, texCoordMax); glVertex3f(x2, y2, z); glTexCoord2f(0.0f, texCoordMax); glVertex3f(x, y2, z); glEnd(); glDisable(GL_BLEND); PROFILE_START("minimap units"); std::vector vertexArray; // TODO: don't reallocate this after every frame (but don't waste memory // after the number of units decreases substantially) // Don't enable GL_POINT_SMOOTH because it's far too slow // (~70msec/frame on a GF4 rendering a thousand points) glPointSize(3.f); if (g_UseSimulation2) { float sx = m_scaleX / CELL_SIZE; float sy = m_scaleY / CELL_SIZE; CSimulation2* sim = g_Game->GetSimulation2(); const CSimulation2::InterfaceList& ents = sim->GetEntitiesWithInterface(IID_Minimap); for (CSimulation2::InterfaceList::const_iterator it = ents.begin(); it != ents.end(); ++it) { MinimapUnitVertex v; ICmpMinimap* cmpMinimap = static_cast(it->second); if (cmpMinimap->GetRenderData(v.r, v.g, v.b, v.x, v.y)) { v.a = 255; v.x = x + v.x*sx; v.y = y - v.y*sy; vertexArray.push_back(v); } } } else { // Draw unit points const std::vector &units = m_UnitManager->GetUnits(); std::vector::const_iterator iter = units.begin(); CUnit *unit = 0; CVector2D pos; CLOSManager* losMgr = g_Game->GetWorld()->GetLOSManager(); for(; iter != units.end(); ++iter) { unit = (CUnit *)(*iter); if(unit && unit->GetEntity() && losMgr->GetUnitStatus(unit, g_Game->GetLocalPlayer()) != UNIT_HIDDEN) { CEntity* entity = unit->GetEntity(); CStrW& type = entity->m_base->m_minimapType; MinimapUnitVertex v; if(type==L"Unit" || type==L"Structure" || type==L"Hero") { // Use the player colour const SPlayerColour& colour = entity->GetPlayer()->GetColour(); v.r = cpu_i32FromFloat(colour.r*255.f); v.g = cpu_i32FromFloat(colour.g*255.f); v.b = cpu_i32FromFloat(colour.b*255.f); v.a = 255; } else { CEntityTemplate* base = entity->m_base; v.r = base->m_minimapR; v.g = base->m_minimapG; v.b = base->m_minimapB; v.a = 255; } pos = GetMapSpaceCoords(entity->m_position); v.x = x + pos.x; v.y = y - pos.y; vertexArray.push_back(v); } } } if (!vertexArray.empty()) { glPushMatrix(); glTranslatef(0, 0, z); // Unbind any vertex buffer object, if our card supports VBO's if (g_Renderer.GetCapabilities().m_VBO) { pglBindBufferARB(GL_ARRAY_BUFFER_ARB, 0); } glInterleavedArrays(GL_C4UB_V2F, sizeof(MinimapUnitVertex), &vertexArray[0]); glDrawArrays(GL_POINTS, 0, (GLsizei)vertexArray.size()); glDisableClientState(GL_COLOR_ARRAY); glDisableClientState(GL_VERTEX_ARRAY); glPopMatrix(); } PROFILE_END("minimap units"); DrawViewRect(); // Reset everything back to normal glPointSize(1.0f); glEnable(GL_TEXTURE_2D); glEnable(GL_DEPTH_TEST); } void CMiniMap::CreateTextures() { Destroy(); // Create terrain texture glGenTextures(1, &m_TerrainTexture); g_Renderer.BindTexture(0, m_TerrainTexture); glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA8, m_TextureSize, m_TextureSize, 0, GL_BGRA_EXT, GL_UNSIGNED_BYTE, 0); m_TerrainData = new u32[(m_MapSize - 1) * (m_MapSize - 1)]; glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_MIN_FILTER,GL_LINEAR); glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_MAG_FILTER,GL_LINEAR); glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_WRAP_S,GL_CLAMP); glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_WRAP_T,GL_CLAMP); // Create LOS texture glGenTextures(1, &m_LOSTexture); g_Renderer.BindTexture(0, m_LOSTexture); glTexImage2D(GL_TEXTURE_2D, 0, GL_ALPHA8, m_TextureSize, m_TextureSize, 0, GL_ALPHA, GL_UNSIGNED_BYTE, 0); m_LOSData = new u8[(m_MapSize - 1) * (m_MapSize - 1)]; glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_MIN_FILTER,GL_LINEAR); glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_MAG_FILTER,GL_LINEAR); glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_WRAP_S,GL_CLAMP); glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_WRAP_T,GL_CLAMP); // Rebuild and upload both of them RebuildTerrainTexture(); RebuildLOSTexture(); } void CMiniMap::RebuildTerrainTexture() { u32 x = 0; u32 y = 0; u32 w = m_MapSize - 1; u32 h = m_MapSize - 1; float waterHeight = g_Renderer.GetWaterManager()->m_WaterHeight; for(u32 j = 0; j < h; j++) { u32 *dataPtr = m_TerrainData + ((y + j) * (m_MapSize - 1)) + x; for(u32 i = 0; i < w; i++) { float avgHeight = ( m_Terrain->GetVertexGroundLevel((int)i, (int)j) + m_Terrain->GetVertexGroundLevel((int)i+1, (int)j) + m_Terrain->GetVertexGroundLevel((int)i, (int)j+1) + m_Terrain->GetVertexGroundLevel((int)i+1, (int)j+1) ) / 4.0f; if(avgHeight < waterHeight) { *dataPtr++ = 0xff304080; // TODO: perhaps use the renderer's water color? } else { int hmap = ((int)m_Terrain->GetHeightMap()[(y + j) * m_MapSize + x + i]) >> 8; int val = (hmap / 3) + 170; u32 color = 0xFFFFFFFF; CMiniPatch *mp = m_Terrain->GetTile(x + i, y + j); if(mp && mp->Tex1) { CTextureEntry *tex = g_TexMan.FindTexture(mp->Tex1); if(tex) color = tex->GetBaseColor(); } *dataPtr++ = ScaleColor(color, float(val) / 255.0f); } } } // Upload the texture g_Renderer.BindTexture(0, m_TerrainTexture); glTexSubImage2D(GL_TEXTURE_2D, 0, 0, 0, m_MapSize - 1, m_MapSize - 1, GL_BGRA_EXT, GL_UNSIGNED_BYTE, m_TerrainData); } void CMiniMap::RebuildLOSTexture() { PROFILE_START("rebuild minimap: los"); CLOSManager* losMgr = g_Game->GetWorld()->GetLOSManager(); CPlayer* player = g_Game->GetLocalPlayer(); ssize_t x = 0; ssize_t y = 0; ssize_t w = m_MapSize - 1; ssize_t h = m_MapSize - 1; for(ssize_t j = 0; j < h; j++) { u8 *dataPtr = m_LOSData + ((y + j) * (m_MapSize - 1)) + x; for(ssize_t i = 0; i < w; i++) { ELOSStatus status = losMgr->GetStatus(i, j, player); if(status == LOS_UNEXPLORED) *dataPtr++ = 0xff; else if(status == LOS_EXPLORED) *dataPtr++ = (u8) (0xff * 0.3f); else *dataPtr++ = 0; } } // Upload the texture g_Renderer.BindTexture(0, m_LOSTexture); glTexSubImage2D(GL_TEXTURE_2D, 0, 0, 0, m_MapSize - 1, m_MapSize - 1, GL_ALPHA, GL_UNSIGNED_BYTE, m_LOSData); PROFILE_END("rebuild minimap: los"); } void CMiniMap::Destroy() { if(m_TerrainTexture) glDeleteTextures(1, &m_TerrainTexture); if(m_LOSTexture) glDeleteTextures(1, &m_LOSTexture); delete[] m_TerrainData; m_TerrainData = 0; delete[] m_LOSData; m_LOSData = 0; } CVector2D CMiniMap::GetMapSpaceCoords(CVector3D worldPos) { float x = rintf(worldPos.X / CELL_SIZE); float y = rintf(worldPos.Z / CELL_SIZE); // Entity's Z coordinate is really its longitudinal coordinate on the terrain // Calculate map space scale return CVector2D(x * m_scaleX, y * m_scaleY); } Index: ps/trunk/source/tools/entconvert/entconvert.pl =================================================================== --- ps/trunk/source/tools/entconvert/entconvert.pl (revision 7483) +++ ps/trunk/source/tools/entconvert/entconvert.pl (revision 7484) @@ -1,335 +1,347 @@ use strict; use warnings; use File::Find; use XML::Simple; use Data::Dumper; my $vfsroot = '../../../binaries/data/mods'; my (%dot_actor, %dot_inherit); my %xml = ('template_entity_full.xml' => 1, 'template_entity_quasi.xml' => 1); convert_all("$vfsroot/public"); convert_all("$vfsroot/internal") if -e "$vfsroot/internal"; sub convert_all { my ($root) = @_; my $dir = "$root/entities"; my $dir2 = "$root/simulation/templates"; my @xml; find({ wanted => sub { push @xml, $_ if /\.xml$/ and !/template_entity(|_full|_quasi)\.xml$/; }, no_chdir => 1 }, $dir); s~\Q$dir/~~ for @xml; $xml{$_} = 1 for @xml; for my $xml (@xml) { print " $xml\n"; my $name = $xml; $name =~ s/\.xml$//; next if $name =~ /^(template_foundation|foundation_)/; my %opt = (KeyAttr => []); my $data = XMLin("$dir/$xml", %opt, ForceArray => 1); my $c = convert($name, $data); my $out = $c; open my $fo, "> $dir2/$xml" or die $!; binmode $fo, ':utf8'; print $fo $out; } } sub convert { my ($name, $data) = @_; #print Dumper $data if $name eq 'template_unit_infantry'; my $out = qq{\n}; my $i = " "; $out .= qq{{Parent}) { my $p = $data->{Parent}; $p = "units/$p" if $p =~ /^(celt|cart|hele|iber|pers|rome)_(cavalry|infantry|support)/; $p = "structures/$p" if $p =~ /^(celt|cart|hele|iber|pers|rome)_scout_tower/; warn "Unknown parent $p\n" unless $xml{"$p.xml"}; $out .= qq{ parent="$p"}; $dot_inherit{$name}{$p} = 1; } $out .= qq{>\n}; my $civ; $civ = 'hele' if $name =~ /^other\/camp_(mace_hypaspist|sparta_phalangite)$/; $civ = 'gaia' if $name =~ /^(template_gaia|template_structure_gaia_settlement|fence_(long|short))$/ or ($name =~ /^gaia\/fauna_/ and $data->{Parent} !~ /^template_gaia/); $civ = $1 if $name =~ /^(?:units|structures)\/([a-z]{4})_/; $civ = $1 if $name =~ /^other\/camp_(pers|rome)_/; my $needs_explicit_civ = ($civ and $data->{Parent} !~ /^${civ}_/); if ($data->{Traits}[0]{Id} or $needs_explicit_civ) { if (not $civ and $name !~ /^template/ and $data->{Parent} =~ /^template/ and $data->{Traits}[0]{Id}[0]{Civ}) { $civ = ({ Hellenes => 'hele', Objects => 'gaia', Romans => 'rome'})->{ $data->{Traits}[0]{Id}[0]{Civ}[0] } or die; $needs_explicit_civ = 1; } $out .= qq{$i\n}; $out .= qq{$i$i$civ\n} if $needs_explicit_civ; my @map = ( [Generic => 'GenericName'], [Specific => 'SpecificName'], [Icon => 'IconSheet'], [Icon_Cell => 'IconCell'], ); for my $m (@map) { $out .= qq{$i$i<$m->[1]>$data->{Traits}[0]{Id}[0]{$m->[0]}[0][1]>\n} if $data->{Traits}[0]{Id}[0]{$m->[0]}; } for my $k (keys %{$data->{Traits}[0]{Id}[0]}) { next if $k =~ /^(Civ)$/; # we do civ based on the filename instead, since it's more reliable next if $k =~ /^(Tooltip|History|Internal_Only|Classes|Rollover|Civ_Code)$/; # TODO: convert these somehow warn "Unrecognised field <$k>" unless grep $_->[0] eq $k, @map; } $out .= qq{$i\n}; } if ($data->{Traits}[0]{MiniMap}) { $out .= qq{$i\n}; $out .= qq{$i$i}.lc($data->{Traits}[0]{MiniMap}[0]{Type}[0]).qq{\n} if $data->{Traits}[0]{MiniMap}[0]{Type}; $out .= qq{$i$i\n} #" if $data->{Traits}[0]{MiniMap}[0]{Red}; $out .= qq{$i\n}; } if ($name eq 'template_structure') { $out .= qq{$i\n}; $out .= qq{$i$istructure\n}; $out .= qq{$i\n}; } if ($name eq 'template_unit') { $out .= qq{$i\n}; $out .= qq{$i\n}; $out .= qq{$i$i1\n}; $out .= qq{$i$i\n}; $out .= qq{$i$i$i0\n}; $out .= qq{$i$i$i0\n}; $out .= qq{$i$i$i0\n}; $out .= qq{$i$i$i0\n}; $out .= qq{$i$i\n}; $out .= qq{$i\n}; } if ($data->{Traits}[0]{Population} or $data->{Traits}[0]{Creation}[0]{Resource} or $data->{Traits}[0]{Creation}[0]{Time}) { $out .= qq{$i\n}; $out .= qq{$i$i$data->{Traits}[0]{Population}[0]{Rem}[0]\n} if defined $data->{Traits}[0]{Population}[0]{Rem} and $data->{Traits}[0]{Population}[0]{Rem}[0] != 1; $out .= qq{$i$i$data->{Traits}[0]{Population}[0]{Add}[0]\n} if defined $data->{Traits}[0]{Population}[0]{Add}; $out .= qq{$i$i$data->{Traits}[0]{Creation}[0]{Time}[0]\n} if defined $data->{Traits}[0]{Creation}[0]{Time}; if ($data->{Traits}[0]{Creation}[0]{Resource}) { $out .= qq{$i$i\n}; for (qw(Food Wood Stone Metal)) { $out .= qq{$i$i$i<\l$_>$data->{Traits}[0]{Creation}[0]{Resource}[0]{$_}[0]\n} if defined $data->{Traits}[0]{Creation}[0]{Resource}[0]{$_}[0]; } $out .= qq{$i$i\n}; } $out .= qq{$i\n}; } if ($data->{Traits}[0]{Supply} and $name =~ /template_gaia/) { $out .= qq{$i\n}; } if ($data->{Traits}[0]{Supply}) { $out .= qq{$i\n}; $out .= qq{$i$i$data->{Traits}[0]{Supply}[0]{Max}[0]\n}; my $t = $data->{Traits}[0]{Supply}[0]{Type}[0]; $t .= '.'.$data->{Traits}[0]{Supply}[0]{SubType}[0] if $data->{Traits}[0]{Supply}[0]{SubType}; $out .= qq{$i$i$t\n}; $out .= qq{$i\n}; } if ($data->{Actions}[0]{Gather}) { $out .= qq{$i\n}; my $speed = sprintf '%.1f', $data->{Actions}[0]{Gather}[0]{Speed}[0]/1000; $out .= qq{$i$i$speed\n}; if ($data->{Actions}[0]{Gather}[0]{Resource}) { $out .= qq{$i$i\n}; my $r = $data->{Actions}[0]{Gather}[0]{Resource}[0]; for my $t (sort keys %$r) { if (ref $r->{$t}[0]) { for my $s (sort keys %{$r->{$t}[0]}) { $out .= qq{$i$i$i<\L$t.$s>$r->{$t}[0]{$s}[0]\n}; } } else { $out .= qq{$i$i$i<\L$t>$r->{$t}[0]\n}; } } $out .= qq{$i$i\n}; } $out .= qq{$i\n}; } if ($data->{Traits}[0]{Health}) { $out .= qq{$i\n}; $out .= qq{$i$icorpse\n} if $name eq 'template_unit'; $out .= qq{$i$ivanish\n} if $name =~ /^(template_structure|other\/fence_(long|short))$/; $out .= qq{$i$i$data->{Traits}[0]{Health}[0]{Max}[0]\n} if $data->{Traits}[0]{Health}[0]{Max}; $out .= qq{$i$i$data->{Traits}[0]{Health}[0]{RegenRate}[0]\n} if $data->{Traits}[0]{Health}[0]{RegenRate}; $out .= qq{$i\n}; } if ($data->{Traits}[0]{Armour}) { $out .= qq{$i\n}; for my $n (qw(Hack Pierce Crush)) { $out .= qq{$i$i<$n>$data->{Traits}[0]{Armour}[0]{$n}[0]\n} if defined $data->{Traits}[0]{Armour}[0]{$n}; } $out .= qq{$i\n}; } if ($data->{Actions}[0]{Move}) { $out .= qq{$i\n}; $out .= qq{$i$i$data->{Actions}[0]{Move}[0]{Speed}[0]\n} if $data->{Actions}[0]{Move}[0]{Speed}; $out .= qq{$i\n}; } die if $data->{Actions}[0]{Attack}[0]{Melee} and $data->{Actions}[0]{Attack}[0]{Ranged}; # only allow one at once my $attack = $data->{Actions}[0]{Attack}[0]{Melee} || $data->{Actions}[0]{Attack}[0]{Ranged}; if ($attack) { $out .= qq{$i\n}; for my $n (qw(Hack Pierce Crush Range MinRange ProjectileSpeed)) { my $e = $n; $e = 'MaxRange' if $e eq 'Range'; $out .= qq{$i$i<$e>$attack->[0]{$n}[0]\n} if $attack->[0]{$n}; $out .= qq{$i$i<$e>0.0\n} if $n eq 'MinRange' and $name =~ /^(template_unit_(cavalry_melee|hero|infantry_melee|mechanical_siege_(ballista|onager|ram)|super_(cavalry|infantry))|units\/celt_support_female_citizen)$/; } if ($attack->[0]{Speed}) { my $s = $attack->[0]{Speed}[0]; # TODO: are these values sane? if ($s eq '1000') { $out .= qq{$i$i600\n}; $out .= qq{$i$i1000\n}; } elsif ($s eq '1500' or $s eq '1520' or $s eq '1510') { $out .= qq{$i$i900\n}; $out .= qq{$i$i1500\n}; } elsif ($s eq '2000') { $out .= qq{$i$i1200\n}; $out .= qq{$i$i2000\n}; } else { die $s; } } $out .= qq{$i\n}; } $dot_actor{$name} = $data->{Actor}; if ($data->{Actor} or $data->{Traits}[0]{Creation}[0]{Foundation}) { $out .= qq{$i\n}; $out .= qq{$i$i$data->{Actor}[0]\n} if $data->{Actor}; if ($data->{Traits}[0]{Creation}[0]{Foundation}) { $data->{Traits}[0]{Creation}[0]{Foundation}[0] =~ /^foundation_(\d+x\d+|theatron|field)$/ or die $data->{Traits}[0]{Creation}[0]{Foundation}[0]; my $actor = ($1 eq 'field' ? 'structures/plot_field_found.xml' : "structures/fndn_$1.xml"); $out .= qq{$i$i$actor\n}; } $out .= qq{$i\n}; } if ($data->{Traits}[0]{Footprint}) { my $r = ''; $r = ' replace=""' if ($data->{Traits}[0]{Footprint}[0]{Width} and $data->{Parent} =~ /^template_(unit|unit_mechanical|unit_mechanical_siege|unit_mechanical_siege_onager|unit_(super|hero)_ranged)$/) or ($data->{Traits}[0]{Footprint}[0]{Radius} and $data->{Parent} =~ /^template_structure_(special|military_fortress)$/); $out .= qq{$i\n}; if ($data->{Traits}[0]{Footprint}[0]{Radius}) { $out .= qq{$i$i\n}; } if ($data->{Traits}[0]{Footprint}[0]{Width}) { $out .= qq{$i$i\n}; #" } if ($data->{Traits}[0]{Footprint}[0]{Height}) { $out .= qq{$i$i$data->{Traits}[0]{Footprint}[0]{Height}[0]\n}; } $out .= qq{$i\n}; - } - if ($name =~ /^template_(structure|gaia)$/) { - $out .= qq{$i\n}; + if ($name =~ /^template_(structure|gaia)_/ and $name !~ /^template_structure_resource_field$/) { + my ($w, $d); + if ($data->{Traits}[0]{Footprint}[0]{Radius}) { + $w = $d = sprintf '%.1f', 2*$data->{Traits}[0]{Footprint}[0]{Radius}[0]; + } + if ($data->{Traits}[0]{Footprint}[0]{Width}) { + $w = $data->{Traits}[0]{Footprint}[0]{Width}[0]; + $d = $data->{Traits}[0]{Footprint}[0]{Depth}[0]; + } + $out .= qq{$i\n}; + $out .= qq{$i$i\n}; + $out .= qq{$i\n}; + } } - if ($name =~ /^template_structure_resource_field$/) { - $out .= qq{$i\n}; + if ($name eq 'template_unit') { + $out .= qq{$i\n}; + $out .= qq{$i$i\n}; + $out .= qq{$i\n}; } if ($data->{Actions}[0]{Create}[0]{List}[0]{StructCiv} or $data->{Actions}[0]{Create}[0]{List}[0]{StructMil}) { $out .= qq{$i\n}; $out .= qq{$i$i1.0\n} if $data->{Actions}[0]{Build}; # $out .= qq{$i$i\n}; $out .= qq{$i$i\n}; for (sort (keys %{$data->{Actions}[0]{Create}[0]{List}[0]{StructCiv}[0]}, keys %{$data->{Actions}[0]{Create}[0]{List}[0]{StructMil}[0]})) { my $n = "structures/" . ($civ || "{civ}") . "_" . (lc $_); $out .= qq{$i$i$i$n\n}; } $out .= qq{$i$i\n}; $out .= qq{$i\n}; } if ($data->{Actions}[0]{Create}[0]{List}[0]{Train}) { $out .= qq{$i\n}; # $out .= qq{$i$i\n}; $out .= qq{$i$i\n}; for (sort (keys %{$data->{Actions}[0]{Create}[0]{List}[0]{Train}[0]})) { my $n = "units/" . ($civ || "{civ}") . "_" . (lc $_); $out .= qq{$i$i$i$n\n}; } $out .= qq{$i$i\n}; $out .= qq{$i\n}; } if ($data->{SoundGroups}) { $out .= qq{$i\n}; $out .= qq{$i$i\n}; for my $n (qw(Walk Run Melee Death Build Gather_Fruit Gather_Grain Gather_Wood Gather_Stone Gather_Metal)) { my $n2 = lc $n; if ($n2 eq 'melee') { $n2 = 'attack'; } if ($data->{SoundGroups}[0]{$n}) { my $f = $data->{SoundGroups}[0]{$n}[0]; $f =~ s~^audio/~~ or die; $out .= qq{$i$i$i<$n2>$f\n}; } } $out .= qq{$i$i\n}; $out .= qq{$i\n}; } $out .= qq{\n}; return $out; } open my $dot, '> entities.dot' or die $!; print $dot < "$_";\n}; } for my $p (sort keys %dot_inherit) { for my $c (sort keys %{$dot_inherit{$p}}) { print $dot qq{"$p" -> "$c";\n}; } } print $dot "}\n"; Index: ps/trunk/source/graphics/Terrain.cpp =================================================================== --- ps/trunk/source/graphics/Terrain.cpp (revision 7483) +++ ps/trunk/source/graphics/Terrain.cpp (revision 7484) @@ -1,565 +1,566 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ /* * Describes ground via heightmap and array of CPatch. */ #include "precompiled.h" #include "lib/res/graphics/ogl_tex.h" +#include "lib/sysdep/cpu.h" #include "renderer/Renderer.h" #include "renderer/WaterManager.h" #include "simulation/Entity.h" #include "TerrainProperties.h" #include "TextureEntry.h" #include "TextureManager.h" #include #include "Terrain.h" #include "Patch.h" #include "maths/FixedVector3D.h" #include "maths/MathUtil.h" #include "ps/CLogger.h" /////////////////////////////////////////////////////////////////////////////// // CTerrain constructor CTerrain::CTerrain() : m_Heightmap(0), m_Patches(0), m_MapSize(0), m_MapSizePatches(0), m_BaseColour(255, 255, 255, 255) { } /////////////////////////////////////////////////////////////////////////////// // CTerrain constructor CTerrain::~CTerrain() { ReleaseData(); } /////////////////////////////////////////////////////////////////////////////// // ReleaseData: delete any data allocated by this terrain void CTerrain::ReleaseData() { delete[] m_Heightmap; delete[] m_Patches; } /////////////////////////////////////////////////////////////////////////////// // Initialise: initialise this terrain to the given size // using given heightmap to setup elevation data bool CTerrain::Initialize(ssize_t patchesPerSide,const u16* data) { // clean up any previous terrain ReleaseData(); // store terrain size m_MapSize=patchesPerSide*PATCH_SIZE+1; m_MapSizePatches=patchesPerSide; // allocate data for new terrain m_Heightmap=new u16[m_MapSize*m_MapSize]; m_Patches=new CPatch[m_MapSizePatches*m_MapSizePatches]; // given a heightmap? if (data) { // yes; keep a copy of it cpu_memcpy(m_Heightmap,data,m_MapSize*m_MapSize*sizeof(u16)); } else { // build a flat terrain memset(m_Heightmap,0,m_MapSize*m_MapSize*sizeof(u16)); } // setup patch parents, indices etc InitialisePatches(); return true; } /////////////////////////////////////////////////////////////////////////////// float CTerrain::GetExactGroundLevel(const CVector2D& v) const { return GetExactGroundLevel(v.x, v.y); } bool CTerrain::IsOnMap(const CVector2D& v) const { return IsOnMap(v.x, v.y); } bool CTerrain::IsPassable(const CVector2D &loc/*tile space*/, HEntity entity) const { CMiniPatch *pTile = GetTile(loc.x, loc.y); if(!pTile) { LOGWARNING(L"IsPassable: invalid coordinates %.1f %.1f\n", loc.x, loc.y); return false; } if(!pTile->Tex1) return false; // Invalid terrain type in the scenario file CTextureEntry *pTexEntry = g_TexMan.FindTexture(pTile->Tex1); CTerrainPropertiesPtr pProperties = pTexEntry->GetProperties(); if(!pProperties) { VfsPath texturePath = pTexEntry->GetTexturePath(); LOGWARNING(L"IsPassable: no properties loaded for %ls\n", texturePath.string().c_str()); return false; } return pProperties->IsPassable(entity); } /////////////////////////////////////////////////////////////////////////////// // CalcPosition: calculate the world space position of the vertex at (i,j) void CTerrain::CalcPosition(ssize_t i, ssize_t j, CVector3D& pos) const { u16 height; if ((size_t)i < (size_t)m_MapSize && (size_t)j < (size_t)m_MapSize) // will reject negative coordinates height = m_Heightmap[j*m_MapSize + i]; else height = 0; pos.X = float(i*CELL_SIZE); pos.Y = float(height*HEIGHT_SCALE); pos.Z = float(j*CELL_SIZE); } /////////////////////////////////////////////////////////////////////////////// // CalcPositionFixed: calculate the world space position of the vertex at (i,j) void CTerrain::CalcPositionFixed(ssize_t i, ssize_t j, CFixedVector3D& pos) const { u16 height; if ((size_t)i < (size_t)m_MapSize && (size_t)j < (size_t)m_MapSize) // will reject negative coordinates height = m_Heightmap[j*m_MapSize + i]; else height = 0; - pos.X = CFixed_23_8::FromInt(i)*CELL_SIZE; - pos.Y = CFixed_23_8::FromInt(height)/HEIGHT_UNITS_PER_METRE; - pos.Z = CFixed_23_8::FromInt(j)*CELL_SIZE; + pos.X = CFixed_23_8::FromInt(i)*(int)CELL_SIZE; + pos.Y = CFixed_23_8::FromInt(height)/(int)HEIGHT_UNITS_PER_METRE; + pos.Z = CFixed_23_8::FromInt(j)*(int)CELL_SIZE; } /////////////////////////////////////////////////////////////////////////////// // CalcNormal: calculate the world space normal of the vertex at (i,j) void CTerrain::CalcNormal(ssize_t i, ssize_t j, CVector3D& normal) const { CVector3D left, right, up, down; // Calculate normals of the four half-tile triangles surrounding this vertex: // get position of vertex where normal is being evaluated CVector3D basepos; CalcPosition(i, j, basepos); if (i > 0) { CalcPosition(i-1, j, left); left -= basepos; left.Normalize(); } if (i < m_MapSize-1) { CalcPosition(i+1, j, right); right -= basepos; right.Normalize(); } if (j > 0) { CalcPosition(i, j-1, up); up -= basepos; up.Normalize(); } if (j < m_MapSize-1) { CalcPosition(i, j+1, down); down -= basepos; down.Normalize(); } CVector3D n0 = up.Cross(left); CVector3D n1 = left.Cross(down); CVector3D n2 = down.Cross(right); CVector3D n3 = right.Cross(up); // Compute the mean of the normals normal = n0 + n1 + n2 + n3; float nlen=normal.Length(); if (nlen>0.00001f) normal*=1.0f/nlen; } /////////////////////////////////////////////////////////////////////////////// // CalcNormalFixed: calculate the world space normal of the vertex at (i,j) void CTerrain::CalcNormalFixed(ssize_t i, ssize_t j, CFixedVector3D& normal) const { CFixedVector3D left, right, up, down; // Calculate normals of the four half-tile triangles surrounding this vertex: // get position of vertex where normal is being evaluated CFixedVector3D basepos; CalcPositionFixed(i, j, basepos); if (i > 0) { CalcPositionFixed(i-1, j, left); left -= basepos; left.Normalize(); } if (i < m_MapSize-1) { CalcPositionFixed(i+1, j, right); right -= basepos; right.Normalize(); } if (j > 0) { CalcPositionFixed(i, j-1, up); up -= basepos; up.Normalize(); } if (j < m_MapSize-1) { CalcPositionFixed(i, j+1, down); down -= basepos; down.Normalize(); } CFixedVector3D n0 = up.Cross(left); CFixedVector3D n1 = left.Cross(down); CFixedVector3D n2 = down.Cross(right); CFixedVector3D n3 = right.Cross(up); // Compute the mean of the normals normal = n0 + n1 + n2 + n3; normal.Normalize(); } /////////////////////////////////////////////////////////////////////////////// // GetPatch: return the patch at (i,j) in patch space, or null if the patch is // out of bounds CPatch* CTerrain::GetPatch(ssize_t i, ssize_t j) const { // range check (invalid indices are passed in by the culling and // patch blend code because they iterate from 0..#patches and examine // neighbors without checking if they're already on the edge) if( (size_t)i >= (size_t)m_MapSizePatches || (size_t)j >= (size_t)m_MapSizePatches ) return 0; return &m_Patches[(j*m_MapSizePatches)+i]; } /////////////////////////////////////////////////////////////////////////////// // GetTile: return the tile at (i,j) in tile space, or null if the tile is out // of bounds CMiniPatch* CTerrain::GetTile(ssize_t i, ssize_t j) const { // see comment above if( (size_t)i >= (size_t)(m_MapSize-1) || (size_t)j >= (size_t)(m_MapSize-1) ) return 0; CPatch* patch=GetPatch(i/PATCH_SIZE, j/PATCH_SIZE); // can't fail (due to above check) return &patch->m_MiniPatches[j%PATCH_SIZE][i%PATCH_SIZE]; } float CTerrain::GetVertexGroundLevel(ssize_t i, ssize_t j) const { i = clamp(i, (ssize_t)0, m_MapSize-1); j = clamp(j, (ssize_t)0, m_MapSize-1); return HEIGHT_SCALE * m_Heightmap[j*m_MapSize + i]; } float CTerrain::GetSlope(float x, float z) const { // Clamp to size-2 so we can use the tiles (xi,zi)-(xi+1,zi+1) const ssize_t xi = clamp((ssize_t)floor(x/CELL_SIZE), (ssize_t)0, m_MapSize-2); const ssize_t zi = clamp((ssize_t)floor(z/CELL_SIZE), (ssize_t)0, m_MapSize-2); float h00 = m_Heightmap[zi*m_MapSize + xi]; float h01 = m_Heightmap[(zi+1)*m_MapSize + xi]; float h10 = m_Heightmap[zi*m_MapSize + (xi+1)]; float h11 = m_Heightmap[(zi+1)*m_MapSize + (xi+1)]; // Difference of highest point from lowest point return std::max(std::max(h00, h01), std::max(h10, h11)) - std::min(std::min(h00, h01), std::min(h10, h11)); } CVector2D CTerrain::GetSlopeAngleFace( CEntity* entity ) const { CVector2D ret; const float D = 0.1f; // Amount to look forward to calculate the slope float x = entity->m_position.X; float z = entity->m_position.Z; // Get forward slope and use it as the x angle CVector2D d = entity->m_ahead.Normalize() * D; float dy = GetExactGroundLevel(x+d.x, z+d.y) - GetExactGroundLevel(x-d.x, z-d.y); ret.x = atan2(dy, 2*D); // Get sideways slope and use it as the y angle CVector2D d2(-d.y, d.x); float dy2 = GetExactGroundLevel(x+d2.x, z+d2.y) - GetExactGroundLevel(x-d2.x, z-d2.y); ret.y = atan2(dy2, 2*D); return ret; } float CTerrain::GetExactGroundLevel(float x, float z) const { // Clamp to size-2 so we can use the tiles (xi,zi)-(xi+1,zi+1) const ssize_t xi = clamp((ssize_t)floor(x/CELL_SIZE), (ssize_t)0, m_MapSize-2); const ssize_t zi = clamp((ssize_t)floor(z/CELL_SIZE), (ssize_t)0, m_MapSize-2); const float xf = clamp(x/CELL_SIZE-xi, 0.0f, 1.0f); const float zf = clamp(z/CELL_SIZE-zi, 0.0f, 1.0f); float h00 = m_Heightmap[zi*m_MapSize + xi]; float h01 = m_Heightmap[(zi+1)*m_MapSize + xi]; float h10 = m_Heightmap[zi*m_MapSize + (xi+1)]; float h11 = m_Heightmap[(zi+1)*m_MapSize + (xi+1)]; // Linearly interpolate return (HEIGHT_SCALE * ( (1 - zf) * ((1 - xf) * h00 + xf * h10) + zf * ((1 - xf) * h01 + xf * h11))); } CFixed_23_8 CTerrain::GetExactGroundLevelFixed(CFixed_23_8 x, CFixed_23_8 z) const { // Clamp to size-2 so we can use the tiles (xi,zi)-(xi+1,zi+1) - const ssize_t xi = clamp((ssize_t)(x/CELL_SIZE).ToInt_RoundToZero(), (ssize_t)0, m_MapSize-2); - const ssize_t zi = clamp((ssize_t)(z/CELL_SIZE).ToInt_RoundToZero(), (ssize_t)0, m_MapSize-2); + const ssize_t xi = clamp((ssize_t)(x / (int)CELL_SIZE).ToInt_RoundToZero(), (ssize_t)0, m_MapSize-2); + const ssize_t zi = clamp((ssize_t)(z / (int)CELL_SIZE).ToInt_RoundToZero(), (ssize_t)0, m_MapSize-2); const CFixed_23_8 one = CFixed_23_8::FromInt(1); - const CFixed_23_8 xf = clamp((x/CELL_SIZE)-CFixed_23_8::FromInt(xi), CFixed_23_8::FromInt(0), one); - const CFixed_23_8 zf = clamp((z/CELL_SIZE)-CFixed_23_8::FromInt(zi), CFixed_23_8::FromInt(0), one); + const CFixed_23_8 xf = clamp((x / (int)CELL_SIZE) - CFixed_23_8::FromInt(xi), CFixed_23_8::FromInt(0), one); + const CFixed_23_8 zf = clamp((z / (int)CELL_SIZE) - CFixed_23_8::FromInt(zi), CFixed_23_8::FromInt(0), one); u16 h00 = m_Heightmap[zi*m_MapSize + xi]; u16 h01 = m_Heightmap[(zi+1)*m_MapSize + xi]; u16 h10 = m_Heightmap[zi*m_MapSize + (xi+1)]; u16 h11 = m_Heightmap[(zi+1)*m_MapSize + (xi+1)]; // Linearly interpolate return ((one - zf).Multiply((one - xf) * h00 + xf * h10) - + zf.Multiply((one - xf) * h01 + xf * h11)) / HEIGHT_UNITS_PER_METRE; + + zf.Multiply((one - xf) * h01 + xf * h11)) / (int)HEIGHT_UNITS_PER_METRE; } /////////////////////////////////////////////////////////////////////////////// // Resize: resize this terrain to the given size (in patches per side) void CTerrain::Resize(ssize_t size) { if (size==m_MapSizePatches) { // inexplicable request to resize terrain to the same size .. ignore it return; } if (!m_Heightmap) { // not yet created a terrain; build a default terrain of the given size now Initialize(size,0); return; } // allocate data for new terrain ssize_t newMapSize=size*PATCH_SIZE+1; u16* newHeightmap=new u16[newMapSize*newMapSize]; CPatch* newPatches=new CPatch[size*size]; if (size>m_MapSizePatches) { // new map is bigger than old one - zero the heightmap so we don't get uninitialised // height data along the expanded edges memset(newHeightmap,0,newMapSize*newMapSize*sizeof(u16)); } // now copy over rows of data u16* src=m_Heightmap; u16* dst=newHeightmap; ssize_t copysize=std::min(newMapSize, m_MapSize); for (ssize_t j=0;jm_MapSize) { // extend the last height to the end of the row for (size_t i=0;im_MapSize) { // copy over heights of the last row to any remaining rows src=newHeightmap+((m_MapSize-1)*newMapSize); dst=src+newMapSize; for (ssize_t i=0;im_MapSizePatches) { // copy over the last tile from each column for (ssize_t n=0;nm_MapSizePatches) { // copy over the last tile from each column CPatch* srcpatch=&newPatches[(m_MapSizePatches-1)*size]; CPatch* dstpatch=srcpatch+size; for (ssize_t p=0;p<(ssize_t)size-m_MapSizePatches;p++) { for (ssize_t n=0;n<(ssize_t)size;n++) { for (ssize_t m=0;mm_MiniPatches[15][k]; CMiniPatch& dst=dstpatch->m_MiniPatches[m][k]; dst.Tex1=src.Tex1; dst.Tex1Priority=src.Tex1Priority; } } srcpatch++; dstpatch++; } } } // release all the original data ReleaseData(); // store new data m_Heightmap=newHeightmap; m_Patches=newPatches; m_MapSize=(ssize_t)newMapSize; m_MapSizePatches=(ssize_t)size; // initialise all the new patches InitialisePatches(); } /////////////////////////////////////////////////////////////////////////////// // InitialisePatches: initialise patch data void CTerrain::InitialisePatches() { for (ssize_t j=0;jInitialize(this,i,j); } } } /////////////////////////////////////////////////////////////////////////////// // SetHeightMap: set up a new heightmap from 16-bit source data; // assumes heightmap matches current terrain size void CTerrain::SetHeightMap(u16* heightmap) { // keep a copy of the given heightmap cpu_memcpy(m_Heightmap,heightmap,m_MapSize*m_MapSize*sizeof(u16)); // recalculate patch bounds, invalidate vertices for (ssize_t j=0;jInvalidateBounds(); patch->SetDirty(RENDERDATA_UPDATE_VERTICES); } } } /////////////////////////////////////////////////////////////////////////////// // FlattenArea: flatten out an area of terrain (specified in world space // coords); return the average height of the flattened area float CTerrain::FlattenArea(float x0, float x1, float z0, float z1) { const ssize_t tx0 = clamp(ssize_t(x0/CELL_SIZE), (ssize_t)0, m_MapSize-1); const ssize_t tx1 = clamp(ssize_t(x1/CELL_SIZE)+1, (ssize_t)0, m_MapSize-1); const ssize_t tz0 = clamp(ssize_t(z0/CELL_SIZE), (ssize_t)0, m_MapSize-1); const ssize_t tz1 = clamp(ssize_t(z1/CELL_SIZE)+1, (ssize_t)0, m_MapSize-1); size_t count=0; double sum=0.0f; for (ssize_t z=tz0;z<=tz1;z++) { for (ssize_t x=tx0;x<=tx1;x++) { sum+=m_Heightmap[z*m_MapSize + x]; count++; } } const u16 avgY = u16(sum/count); for (ssize_t z=tz0;z<=tz1;z++) { for (ssize_t x=tx0;x<=tx1;x++) { m_Heightmap[z*m_MapSize + x]=avgY; } } MakeDirty(tx0, tz0, tx1, tz1, RENDERDATA_UPDATE_VERTICES); return avgY*HEIGHT_SCALE; } /////////////////////////////////////////////////////////////////////////////// void CTerrain::MakeDirty(ssize_t i0, ssize_t j0, ssize_t i1, ssize_t j1, int dirtyFlags) { // flag vertex data as dirty for affected patches, and rebuild bounds of these patches ssize_t pi0 = clamp((i0/PATCH_SIZE)-1, (ssize_t)0, m_MapSizePatches); ssize_t pi1 = clamp((i1/PATCH_SIZE)+1, (ssize_t)0, m_MapSizePatches); ssize_t pj0 = clamp((j0/PATCH_SIZE)-1, (ssize_t)0, m_MapSizePatches); ssize_t pj1 = clamp((j1/PATCH_SIZE)+1, (ssize_t)0, m_MapSizePatches); for (ssize_t j = pj0; j < pj1; j++) { for (ssize_t i = pi0; i < pi1; i++) { CPatch* patch = GetPatch(i,j); // can't fail (i,j were clamped) if (dirtyFlags & RENDERDATA_UPDATE_VERTICES) patch->CalcBounds(); patch->SetDirty(dirtyFlags); } } } void CTerrain::MakeDirty(int dirtyFlags) { for (ssize_t j = 0; j < m_MapSizePatches; j++) { for (ssize_t i = 0; i < m_MapSizePatches; i++) { CPatch* patch = GetPatch(i,j); // can't fail if (dirtyFlags & RENDERDATA_UPDATE_VERTICES) patch->CalcBounds(); patch->SetDirty(dirtyFlags); } } } Index: ps/trunk/source/graphics/Terrain.h =================================================================== --- ps/trunk/source/graphics/Terrain.h (revision 7483) +++ ps/trunk/source/graphics/Terrain.h (revision 7484) @@ -1,157 +1,156 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ /* * Describes ground via heightmap and array of CPatch. */ #ifndef INCLUDED_TERRAIN #define INCLUDED_TERRAIN #include "maths/Vector3D.h" #include "maths/Fixed.h" #include "graphics/SColor.h" -#include "lib/sysdep/cpu.h" class HEntity; class CEntity; class CPatch; class CMiniPatch; class CVector2D; class CFixedVector3D; /////////////////////////////////////////////////////////////////////////////// // Terrain Constants: /// metres [world space units] per tile in x and z const ssize_t CELL_SIZE = 4; /// number of u16 height units per metre const ssize_t HEIGHT_UNITS_PER_METRE = 731; // == int(256.0f/0.35f) /// metres per u16 height unit const float HEIGHT_SCALE = 1.f / HEIGHT_UNITS_PER_METRE; /////////////////////////////////////////////////////////////////////////////// // CTerrain: main terrain class; contains the heightmap describing elevation // data, and the smaller subpatches that form the terrain class CTerrain { public: CTerrain(); ~CTerrain(); // Coordinate naming convention: world-space coordinates are float x,z; // tile-space coordinates are ssize_t i,j. rationale: signed types can // more efficiently be converted to/from floating point. use ssize_t // instead of int/long because these are sizes. bool Initialize(ssize_t patchesPerSide, const u16* ptr); // return number of vertices along edge of the terrain ssize_t GetVerticesPerSide() const { return m_MapSize; } // return number of tiles along edge of the terrain ssize_t GetTilesPerSide() const { return GetVerticesPerSide()-1; } // return number of patches along edge of the terrain ssize_t GetPatchesPerSide() const { return m_MapSizePatches; } bool IsOnMap(float x, float z) const { return ((x >= 0.0f) && (x < (float)((m_MapSize-1) * CELL_SIZE)) && (z >= 0.0f) && (z < (float)((m_MapSize-1) * CELL_SIZE))); } bool IsOnMap(const CVector2D& v) const; bool IsPassable(const CVector2D& tileSpaceLoc, HEntity entity) const; float GetVertexGroundLevel(ssize_t i, ssize_t j) const; float GetExactGroundLevel(float x, float z) const; CFixed_23_8 GetExactGroundLevelFixed(CFixed_23_8 x, CFixed_23_8 z) const; float GetExactGroundLevel(const CVector2D& v) const; float GetSlope(float x, float z) const ; //Find the slope of in X and Z axes depending on the way the entity is facing CVector2D GetSlopeAngleFace(CEntity* entity) const; // resize this terrain such that each side has given number of patches void Resize(ssize_t size); // set up a new heightmap from 16 bit data; assumes heightmap matches current terrain size void SetHeightMap(u16* heightmap); // return a pointer to the heightmap u16* GetHeightMap() const { return m_Heightmap; } // get patch at given coordinates, expressed in patch-space; return 0 if // coordinates represent patch off the edge of the map CPatch* GetPatch(ssize_t i, ssize_t j) const; // get tile at given coordinates, expressed in tile-space; return 0 if // coordinates represent tile off the edge of the map CMiniPatch* GetTile(ssize_t i, ssize_t j) const; // calculate the position of a given vertex void CalcPosition(ssize_t i, ssize_t j, CVector3D& pos) const; void CalcPositionFixed(ssize_t i, ssize_t j, CFixedVector3D& pos) const; // calculate the vertex under a given position (rounding down coordinates) static void CalcFromPosition(const CVector3D& pos, ssize_t& i, ssize_t& j) { i = (ssize_t)(pos.X/CELL_SIZE); j = (ssize_t)(pos.Z/CELL_SIZE); } // calculate the vertex under a given position (rounding down coordinates) static void CalcFromPosition(float x, float z, ssize_t& i, ssize_t& j) { i = (ssize_t)(x/CELL_SIZE); j = (ssize_t)(z/CELL_SIZE); } // calculate the normal at a given vertex void CalcNormal(ssize_t i, ssize_t j, CVector3D& normal) const; void CalcNormalFixed(ssize_t i, ssize_t j, CFixedVector3D& normal) const; // flatten out an area of terrain (specified in world space coords); return // the average height of the flattened area float FlattenArea(float x0, float x1, float z0, float z1); // mark a specific square of tiles as dirty - use this after modifying the heightmap void MakeDirty(ssize_t i0, ssize_t j0, ssize_t i1, ssize_t j1, int dirtyFlags); // mark the entire map as dirty void MakeDirty(int dirtyFlags); // get the base colour for the terrain (typically pure white - other colours // will interact badly with LOS - but used by the Actor Viewer tool) SColor4ub GetBaseColour() const { return m_BaseColour; } // set the base colour for the terrain void SetBaseColour(SColor4ub colour) { m_BaseColour = colour; } private: // delete any data allocated by this terrain void ReleaseData(); // setup patch pointers etc void InitialisePatches(); // size of this map in each direction, in vertices; ie. total tiles = sqr(m_MapSize-1) ssize_t m_MapSize; // size of this map in each direction, in patches; total patches = sqr(m_MapSizePatches) ssize_t m_MapSizePatches; // the patches comprising this terrain CPatch* m_Patches; // 16-bit heightmap data u16* m_Heightmap; // base colour (usually white) SColor4ub m_BaseColour; }; #endif Index: ps/trunk/source/simulation2/helpers/Render.cpp =================================================================== --- ps/trunk/source/simulation2/helpers/Render.cpp (revision 7483) +++ ps/trunk/source/simulation2/helpers/Render.cpp (revision 7484) @@ -1,82 +1,103 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #include "precompiled.h" #include "Render.h" #include "simulation2/Simulation2.h" #include "simulation2/components/ICmpTerrain.h" #include "graphics/Overlay.h" static const size_t RENDER_CIRCLE_POINTS = 16; static const float RENDER_HEIGHT_DELTA = 0.25f; // distance above terrain +void SimRender::ConstructLineOnGround(const CSimContext& context, std::vector xz, SOverlayLine& overlay) +{ + overlay.m_Coords.clear(); + + CmpPtr cmpTerrain(context, SYSTEM_ENTITY); + if (cmpTerrain.null()) + return; + + overlay.m_Coords.reserve(xz.size()/2 * 3); + + for (size_t i = 0; i < xz.size(); i += 2) + { + float px = xz[i]; + float pz = xz[i+1]; + float py = cmpTerrain->GetGroundLevel(px, pz) + RENDER_HEIGHT_DELTA; + overlay.m_Coords.push_back(px); + overlay.m_Coords.push_back(py); + overlay.m_Coords.push_back(pz); + } +} + void SimRender::ConstructCircleOnGround(const CSimContext& context, float x, float z, float radius, SOverlayLine& overlay) { overlay.m_Coords.clear(); CmpPtr cmpTerrain(context, SYSTEM_ENTITY); if (cmpTerrain.null()) return; overlay.m_Coords.reserve((RENDER_CIRCLE_POINTS + 1) * 3); for (size_t i = 0; i <= RENDER_CIRCLE_POINTS; ++i) // use '<=' so it's a closed loop { float a = i * 2 * (float)M_PI / RENDER_CIRCLE_POINTS; float px = x + radius * sin(a); float pz = z + radius * cos(a); float py = cmpTerrain->GetGroundLevel(px, pz) + RENDER_HEIGHT_DELTA; overlay.m_Coords.push_back(px); overlay.m_Coords.push_back(py); overlay.m_Coords.push_back(pz); } } void SimRender::ConstructSquareOnGround(const CSimContext& context, float x, float z, float w, float h, float a, SOverlayLine& overlay) { overlay.m_Coords.clear(); CmpPtr cmpTerrain(context, SYSTEM_ENTITY); if (cmpTerrain.null()) return; // TODO: might be nicer to split this into little pieces so it copes better with uneven terrain overlay.m_Coords.reserve(5 * 3); float c = cos(a); float s = sin(a); std::vector > coords; coords.push_back(std::make_pair(x - w/2*c + h/2*s, z + w/2*s + h/2*c)); coords.push_back(std::make_pair(x - w/2*c - h/2*s, z + w/2*s - h/2*c)); coords.push_back(std::make_pair(x + w/2*c - h/2*s, z - w/2*s - h/2*c)); coords.push_back(std::make_pair(x + w/2*c + h/2*s, z - w/2*s + h/2*c)); coords.push_back(std::make_pair(x - w/2*c + h/2*s, z + w/2*s + h/2*c)); for (size_t i = 0; i < coords.size(); ++i) { float px = coords[i].first; float pz = coords[i].second; float py = cmpTerrain->GetGroundLevel(px, pz) + RENDER_HEIGHT_DELTA; overlay.m_Coords.push_back(px); overlay.m_Coords.push_back(py); overlay.m_Coords.push_back(pz); } } Index: ps/trunk/source/simulation2/helpers/Geometry.h =================================================================== --- ps/trunk/source/simulation2/helpers/Geometry.h (nonexistent) +++ ps/trunk/source/simulation2/helpers/Geometry.h (revision 7484) @@ -0,0 +1,51 @@ +/* Copyright (C) 2010 Wildfire Games. + * This file is part of 0 A.D. + * + * 0 A.D. 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. + * + * 0 A.D. 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 0 A.D. If not, see . + */ + +#ifndef INCLUDED_HELPER_GEOMETRY +#define INCLUDED_HELPER_GEOMETRY + +/** + * @file + * Helper functions related to geometry algorithms + */ + +#include "maths/Fixed.h" + +class CFixedVector2D; + +namespace Geometry +{ + +typedef CFixed_23_8 fixed; + +bool PointIsInSquare(CFixedVector2D point, CFixedVector2D u, CFixedVector2D v, CFixedVector2D halfSize); + +CFixedVector2D GetHalfBoundingBox(CFixedVector2D u, CFixedVector2D v, CFixedVector2D halfSize); + +fixed DistanceToSquare(CFixedVector2D point, CFixedVector2D u, CFixedVector2D v, CFixedVector2D halfSize); + +CFixedVector2D NearestPointOnSquare(CFixedVector2D point, CFixedVector2D u, CFixedVector2D v, CFixedVector2D halfSize); + +bool TestRaySquare(CFixedVector2D a, CFixedVector2D b, CFixedVector2D u, CFixedVector2D v, CFixedVector2D halfSize); + +bool TestSquareSquare( + CFixedVector2D c0, CFixedVector2D u0, CFixedVector2D v0, CFixedVector2D halfSize0, + CFixedVector2D c1, CFixedVector2D u1, CFixedVector2D v1, CFixedVector2D halfSize1); + +} // namespace + +#endif // INCLUDED_HELPER_GEOMETRY Index: ps/trunk/source/simulation2/helpers/Render.h =================================================================== --- ps/trunk/source/simulation2/helpers/Render.h (revision 7483) +++ ps/trunk/source/simulation2/helpers/Render.h (revision 7484) @@ -1,45 +1,50 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #ifndef INCLUDED_HELPER_RENDER #define INCLUDED_HELPER_RENDER /** * @file * Helper functions related to rendering */ class CSimContext; struct SOverlayLine; namespace SimRender { /** + * Updates @p overlay so that it represents the given line (a list of x, z coordinate pairs), flattened on the terrain. + */ +void ConstructLineOnGround(const CSimContext& context, std::vector xz, SOverlayLine& overlay); + +/** * Updates @p overlay so that it represents the given circle, flattened on the terrain. */ void ConstructCircleOnGround(const CSimContext& context, float x, float z, float radius, SOverlayLine& overlay); /** * Updates @p overlay so that it represents the given square, flattened on the terrain. * @p x and @p z are position of center, @p w and @p h are size of rectangle, @p a is clockwise angle. */ void ConstructSquareOnGround(const CSimContext& context, float x, float z, float w, float h, float a, SOverlayLine& overlay); } // namespace #endif // INCLUDED_HELPER_RENDER Index: ps/trunk/source/simulation2/helpers/Geometry.cpp =================================================================== --- ps/trunk/source/simulation2/helpers/Geometry.cpp (nonexistent) +++ ps/trunk/source/simulation2/helpers/Geometry.cpp (revision 7484) @@ -0,0 +1,288 @@ +/* Copyright (C) 2010 Wildfire Games. + * This file is part of 0 A.D. + * + * 0 A.D. 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. + * + * 0 A.D. 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 0 A.D. If not, see . + */ + +#include "precompiled.h" + +#include "Geometry.h" + +#include "maths/FixedVector2D.h" + +using namespace Geometry; + +// TODO: all of these things could be optimised quite easily + +bool Geometry::PointIsInSquare(CFixedVector2D point, CFixedVector2D u, CFixedVector2D v, CFixedVector2D halfSize) +{ + CFixed_23_8 du = point.Dot(u); + if (-halfSize.X <= du && du <= halfSize.X) + { + CFixed_23_8 dv = point.Dot(v); + if (-halfSize.Y <= dv && dv <= halfSize.Y) + return true; + } + return false; +} + +CFixedVector2D Geometry::GetHalfBoundingBox(CFixedVector2D u, CFixedVector2D v, CFixedVector2D halfSize) +{ + return CFixedVector2D( + u.X.Multiply(halfSize.X).Absolute() + v.X.Multiply(halfSize.Y).Absolute(), + u.Y.Multiply(halfSize.X).Absolute() + v.Y.Multiply(halfSize.Y).Absolute() + ); +} + +Geometry::fixed Geometry::DistanceToSquare(CFixedVector2D point, CFixedVector2D u, CFixedVector2D v, CFixedVector2D halfSize) +{ + /* + * Relative to its own coordinate system, we have a square like: + * + * A : B : C + * : : + * - - ########### - - + * # # + * # I # + * D # 0 # E v + * # # ^ + * # # | + * - - ########### - - -->u + * : : + * F : G : H + * + * where 0 is the center, u and v are unit axes, + * and the square is hw*2 by hh*2 units in size. + * + * Points in the BIG regions should check distance to horizontal edges. + * Points in the DIE regions should check distance to vertical edges. + * Points in the ACFH regions should check distance to the corresponding corner. + * + * So we just need to check all of the regions to work out which calculations to apply. + * + */ + + // du, dv are the location of the point in the square's coordinate system + fixed du = point.Dot(u); + fixed dv = point.Dot(v); + + fixed hw = halfSize.X; + fixed hh = halfSize.Y; + + // TODO: I haven't actually tested this + + if (-hw < du && du < hw) // regions B, I, G + { + fixed closest = (dv.Absolute() - hh).Absolute(); // horizontal edges + + if (-hh < dv && dv < hh) // region I + closest = std::min(closest, (du.Absolute() - hw).Absolute()); // vertical edges + + return closest; + } + else if (-hh < dv && dv < hh) // regions D, E + { + return (du.Absolute() - hw).Absolute(); // vertical edges + } + else // regions A, C, F, H + { + CFixedVector2D corner; + if (du < fixed::Zero()) // A, F + corner -= u.Multiply(hw); + else // C, H + corner += u.Multiply(hw); + if (dv < fixed::Zero()) // F, H + corner -= v.Multiply(hh); + else // A, C + corner += v.Multiply(hh); + + return (corner - point).Length(); + } +} + +CFixedVector2D Geometry::NearestPointOnSquare(CFixedVector2D point, CFixedVector2D u, CFixedVector2D v, CFixedVector2D halfSize) +{ + /* + * Relative to its own coordinate system, we have a square like: + * + * A : : C + * : : + * - - #### B #### - - + * #\ /# + * # \ / # + * D --0-- E v + * # / \ # ^ + * #/ \# | + * - - #### G #### - - -->u + * : : + * F : : H + * + * where 0 is the center, u and v are unit axes, + * and the square is hw*2 by hh*2 units in size. + * + * Points in the BDEG regions are nearest to the corresponding edge. + * Points in the ACFH regions are nearest to the corresponding corner. + * + * So we just need to check all of the regions to work out which calculations to apply. + * + */ + + // du, dv are the location of the point in the square's coordinate system + fixed du = point.Dot(u); + fixed dv = point.Dot(v); + + fixed hw = halfSize.X; + fixed hh = halfSize.Y; + + if (-hw < du && du < hw) // regions B, G; or regions D, E inside the square + { + if (-hh < dv && dv < hh && (du.Absolute() - hw).Absolute() < (dv.Absolute() - hh).Absolute()) // regions D, E + { + if (du >= fixed::Zero()) // E + return u.Multiply(hw) + v.Multiply(dv); + else // D + return -u.Multiply(hw) + v.Multiply(dv); + } + else // B, G + { + if (dv >= fixed::Zero()) // B + return v.Multiply(hh) + u.Multiply(du); + else // G + return -v.Multiply(hh) + u.Multiply(du); + } + } + else if (-hh < dv && dv < hh) // regions D, E outside the square + { + if (du >= fixed::Zero()) // E + return u.Multiply(hw) + v.Multiply(dv); + else // D + return -u.Multiply(hw) + v.Multiply(dv); + } + else // regions A, C, F, H + { + CFixedVector2D corner; + if (du < fixed::Zero()) // A, F + corner -= u.Multiply(hw); + else // C, H + corner += u.Multiply(hw); + if (dv < fixed::Zero()) // F, H + corner -= v.Multiply(hh); + else // A, C + corner += v.Multiply(hh); + + return corner; + } +} + +bool Geometry::TestRaySquare(CFixedVector2D a, CFixedVector2D b, CFixedVector2D u, CFixedVector2D v, CFixedVector2D halfSize) +{ + /* + * We only consider collisions to be when the ray goes from outside to inside the shape (and possibly out again). + * Various cases to consider: + * 'a' inside, 'b' inside -> no collision + * 'a' inside, 'b' outside -> no collision + * 'a' outside, 'b' inside -> collision + * 'a' outside, 'b' outside -> depends; use separating axis theorem: + * if the ray's bounding box is outside the square -> no collision + * if the whole square is on the same side of the ray -> no collision + * otherwise -> collision + * (Points on the edge are considered 'inside'.) + */ + + fixed hw = halfSize.X; + fixed hh = halfSize.Y; + + fixed au = a.Dot(u); + fixed av = a.Dot(v); + + if (-hw <= au && au <= hw && -hh <= av && av <= hh) + return false; // a is inside + + fixed bu = b.Dot(u); + fixed bv = b.Dot(v); + + if (-hw <= bu && bu <= hw && -hh <= bv && bv <= hh) // TODO: isn't this subsumed by the next checks? + return true; // a is outside, b is inside + + if ((au < -hw && bu < -hw) || (au > hw && bu > hw) || (av < -hh && bv < -hh) || (av > hh && bv > hh)) + return false; // ab is entirely above/below/side the square + + CFixedVector2D abp = (b - a).Perpendicular(); + fixed s0 = abp.Dot((u.Multiply(hw) + v.Multiply(hh)) - a); + fixed s1 = abp.Dot((u.Multiply(hw) - v.Multiply(hh)) - a); + fixed s2 = abp.Dot((-u.Multiply(hw) - v.Multiply(hh)) - a); + fixed s3 = abp.Dot((-u.Multiply(hw) + v.Multiply(hh)) - a); + if (s0.IsZero() || s1.IsZero() || s2.IsZero() || s3.IsZero()) + return true; // ray intersects the corner + + bool sign = (s0 < fixed::Zero()); + if ((s1 < fixed::Zero()) != sign || (s2 < fixed::Zero()) != sign || (s3 < fixed::Zero()) != sign) + return true; // ray cuts through the square + + return false; +} + +/** + * Separating axis test; returns true if the square defined by u/v/halfSize at the origin + * is not entirely on the clockwise side of a line in direction 'axis' passing through 'a' + */ +static bool SquareSAT(CFixedVector2D a, CFixedVector2D axis, CFixedVector2D u, CFixedVector2D v, CFixedVector2D halfSize) +{ + fixed hw = halfSize.X; + fixed hh = halfSize.Y; + + CFixedVector2D p = axis.Perpendicular(); + if (p.Dot((u.Multiply(hw) + v.Multiply(hh)) - a) <= fixed::Zero()) + return true; + if (p.Dot((u.Multiply(hw) - v.Multiply(hh)) - a) <= fixed::Zero()) + return true; + if (p.Dot((-u.Multiply(hw) - v.Multiply(hh)) - a) <= fixed::Zero()) + return true; + if (p.Dot((-u.Multiply(hw) + v.Multiply(hh)) - a) <= fixed::Zero()) + return true; + + return false; +} + +bool Geometry::TestSquareSquare( + CFixedVector2D c0, CFixedVector2D u0, CFixedVector2D v0, CFixedVector2D halfSize0, + CFixedVector2D c1, CFixedVector2D u1, CFixedVector2D v1, CFixedVector2D halfSize1) +{ + // TODO: need to test this carefully + + CFixedVector2D corner0a = c0 + u0.Multiply(halfSize0.X) + v0.Multiply(halfSize0.Y); + CFixedVector2D corner0b = c0 - u0.Multiply(halfSize0.X) - v0.Multiply(halfSize0.Y); + CFixedVector2D corner1a = c1 + u1.Multiply(halfSize1.X) + v1.Multiply(halfSize1.Y); + CFixedVector2D corner1b = c1 - u1.Multiply(halfSize1.X) - v1.Multiply(halfSize1.Y); + + // Do a SAT test for each square vs each edge of the other square + if (!SquareSAT(corner0a - c1, -u0, u1, v1, halfSize1)) + return false; + if (!SquareSAT(corner0a - c1, v0, u1, v1, halfSize1)) + return false; + if (!SquareSAT(corner0b - c1, u0, u1, v1, halfSize1)) + return false; + if (!SquareSAT(corner0b - c1, -v0, u1, v1, halfSize1)) + return false; + if (!SquareSAT(corner1a - c0, -u1, u0, v0, halfSize0)) + return false; + if (!SquareSAT(corner1a - c0, v1, u0, v0, halfSize0)) + return false; + if (!SquareSAT(corner1b - c0, u1, u0, v0, halfSize0)) + return false; + if (!SquareSAT(corner1b - c0, -v1, u0, v0, halfSize0)) + return false; + + return true; +} Index: ps/trunk/source/simulation2/tests/test_CmpTemplateManager.h =================================================================== --- ps/trunk/source/simulation2/tests/test_CmpTemplateManager.h (revision 7483) +++ ps/trunk/source/simulation2/tests/test_CmpTemplateManager.h (revision 7484) @@ -1,188 +1,188 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #include "lib/self_test.h" #include "simulation2/system/ComponentManager.h" #include "simulation2/components/ICmpTemplateManager.h" #include "simulation2/components/ICmpTest.h" #include "simulation2/MessageTypes.h" #include "simulation2/system/ParamNode.h" #include "simulation2/system/SimContext.h" #include "simulation2/Simulation2.h" #include "graphics/Terrain.h" #include "ps/Filesystem.h" #include "ps/CLogger.h" #include "ps/XML/Xeromyces.h" class TestCmpTemplateManager : public CxxTest::TestSuite { public: void setUp() { g_VFS = CreateVfs(20 * MiB); CXeromyces::Startup(); } void tearDown() { CXeromyces::Terminate(); g_VFS.reset(); } void test_LoadTemplate() { TS_ASSERT_OK(g_VFS->Mount(L"", DataDir()/L"mods/_test.sim")); CSimContext context; CComponentManager man(context); man.LoadComponentTypes(); entity_id_t ent1 = 1, ent2 = 2; CParamNode noParam; TS_ASSERT(man.AddComponent(ent1, CID_TemplateManager, noParam)); ICmpTemplateManager* tempMan = static_cast (man.QueryInterface(ent1, IID_TemplateManager)); TS_ASSERT(tempMan != NULL); const CParamNode* basic = tempMan->LoadTemplate(ent2, L"basic", -1); TS_ASSERT(basic != NULL); TS_ASSERT_WSTR_EQUALS(basic->ToXML(), L"12345"); const CParamNode* inherit2 = tempMan->LoadTemplate(ent2, L"inherit2", -1); TS_ASSERT(inherit2 != NULL); TS_ASSERT_WSTR_EQUALS(inherit2->ToXML(), L"d2e1f1g2"); const CParamNode* inherit1 = tempMan->LoadTemplate(ent2, L"inherit1", -1); TS_ASSERT(inherit1 != NULL); TS_ASSERT_WSTR_EQUALS(inherit1->ToXML(), L"d1e1f1"); const CParamNode* actor = tempMan->LoadTemplate(ent2, L"actor|example1", -1); TS_ASSERT(actor != NULL); TS_ASSERT_WSTR_EQUALS(actor->ToXML(), L"0uprightfalseexample1"); const CParamNode* preview = tempMan->LoadTemplate(ent2, L"preview|unit", -1); TS_ASSERT(preview != NULL); TS_ASSERT_WSTR_EQUALS(preview->ToXML(), L"0uprightfalseexample"); const CParamNode* previewobstruct = tempMan->LoadTemplate(ent2, L"preview|unitobstruct", -1); TS_ASSERT(previewobstruct != NULL); - TS_ASSERT_WSTR_EQUALS(previewobstruct->ToXML(), L"1.00uprightfalseexample"); + TS_ASSERT_WSTR_EQUALS(previewobstruct->ToXML(), L"1.00uprightfalseexample"); const CParamNode* previewactor = tempMan->LoadTemplate(ent2, L"preview|actor|example2", -1); TS_ASSERT(previewactor != NULL); TS_ASSERT_WSTR_EQUALS(previewactor->ToXML(), L"0uprightfalseexample2"); } void test_LoadTemplate_errors() { TS_ASSERT_OK(g_VFS->Mount(L"", DataDir()/L"mods/_test.sim")); CSimContext context; CComponentManager man(context); man.LoadComponentTypes(); entity_id_t ent1 = 1, ent2 = 2; CParamNode noParam; TS_ASSERT(man.AddComponent(ent1, CID_TemplateManager, noParam)); ICmpTemplateManager* tempMan = static_cast (man.QueryInterface(ent1, IID_TemplateManager)); TS_ASSERT(tempMan != NULL); TestLogger logger; TS_ASSERT(tempMan->LoadTemplate(ent2, L"illformed", -1) == NULL); TS_ASSERT(tempMan->LoadTemplate(ent2, L"invalid", -1) == NULL); TS_ASSERT(tempMan->LoadTemplate(ent2, L"nonexistent", -1) == NULL); TS_ASSERT(tempMan->LoadTemplate(ent2, L"inherit-loop", -1) == NULL); TS_ASSERT(tempMan->LoadTemplate(ent2, L"inherit-broken", -1) == NULL); TS_ASSERT(tempMan->LoadTemplate(ent2, L"inherit-special", -1) == NULL); TS_ASSERT(tempMan->LoadTemplate(ent2, L"preview|nonexistent", -1) == NULL); } void test_LoadTemplate_multiple() { TS_ASSERT_OK(g_VFS->Mount(L"", DataDir()/L"mods/_test.sim")); CSimContext context; CComponentManager man(context); man.LoadComponentTypes(); entity_id_t ent1 = 1, ent2 = 2; CParamNode noParam; TS_ASSERT(man.AddComponent(ent1, CID_TemplateManager, noParam)); ICmpTemplateManager* tempMan = static_cast (man.QueryInterface(ent1, IID_TemplateManager)); TS_ASSERT(tempMan != NULL); const CParamNode* basicA = tempMan->LoadTemplate(ent2, L"basic", -1); TS_ASSERT(basicA != NULL); const CParamNode* basicB = tempMan->LoadTemplate(ent2, L"basic", -1); TS_ASSERT(basicA == basicB); const CParamNode* inherit2A = tempMan->LoadTemplate(ent2, L"inherit2", -1); TS_ASSERT(inherit2A != NULL); const CParamNode* inherit2B = tempMan->LoadTemplate(ent2, L"inherit2", -1); TS_ASSERT(inherit2A == inherit2B); TestLogger logger; TS_ASSERT(tempMan->LoadTemplate(ent2, L"nonexistent", -1) == NULL); TS_ASSERT(tempMan->LoadTemplate(ent2, L"nonexistent", -1) == NULL); TS_ASSERT(tempMan->LoadTemplate(ent2, L"inherit-loop", -1) == NULL); TS_ASSERT(tempMan->LoadTemplate(ent2, L"inherit-loop", -1) == NULL); TS_ASSERT(tempMan->LoadTemplate(ent2, L"inherit-broken", -1) == NULL); TS_ASSERT(tempMan->LoadTemplate(ent2, L"inherit-broken", -1) == NULL); } void test_load_all_DISABLED() // disabled since it's a bit slow { TS_ASSERT_OK(g_VFS->Mount(L"", DataDir()/L"mods/public")); CTerrain dummy; CSimulation2 sim(NULL, &dummy); sim.LoadDefaultScripts(); sim.ResetState(); CmpPtr cmpTempMan(sim, SYSTEM_ENTITY); TS_ASSERT(!cmpTempMan.null()); std::vector templates = cmpTempMan->FindAllTemplates(); for (size_t i = 0; i < templates.size(); ++i) { std::wstring name = templates[i]; printf("# %ls\n", name.c_str()); const CParamNode* p = cmpTempMan->GetTemplate(name); TS_ASSERT(p != NULL); } } }; Index: ps/trunk/source/simulation2/TypeList.h =================================================================== --- ps/trunk/source/simulation2/TypeList.h (revision 7483) +++ ps/trunk/source/simulation2/TypeList.h (revision 7484) @@ -1,106 +1,106 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ // MESSAGE: message types // INTERFACE: component interface types // COMPONENT: component types // Components intended only for use in test cases: // (The tests rely on the enum IDs, so don't change the order of these) INTERFACE(Test1) COMPONENT(Test1A) COMPONENT(Test1B) COMPONENT(Test1Scripted) INTERFACE(Test2) COMPONENT(Test2A) COMPONENT(Test2Scripted) // Message types: MESSAGE(TurnStart) MESSAGE(Update) MESSAGE(Interpolate) // non-deterministic (use with caution) MESSAGE(RenderSubmit) // non-deterministic (use with caution) MESSAGE(Destroy) MESSAGE(OwnershipChanged) MESSAGE(PositionChanged) MESSAGE(MotionChanged) // TemplateManager must come before all other (non-test) components, // so that it is the first to be (de)serialized INTERFACE(TemplateManager) COMPONENT(TemplateManager) // Special component for script component types with no native interface INTERFACE(UnknownScript) COMPONENT(UnknownScript) // In alphabetical order: INTERFACE(CommandQueue) COMPONENT(CommandQueue) INTERFACE(Footprint) COMPONENT(Footprint) INTERFACE(GuiInterface) COMPONENT(GuiInterfaceScripted) INTERFACE(Minimap) COMPONENT(Minimap) INTERFACE(Motion) COMPONENT(MotionBall) COMPONENT(MotionScripted) INTERFACE(Obstruction) COMPONENT(Obstruction) INTERFACE(ObstructionManager) COMPONENT(ObstructionManager) INTERFACE(Ownership) COMPONENT(Ownership) INTERFACE(Pathfinder) COMPONENT(Pathfinder) INTERFACE(Player) COMPONENT(PlayerScripted) INTERFACE(PlayerManager) COMPONENT(PlayerManagerScripted) INTERFACE(Position) COMPONENT(Position) // must be before VisualActor INTERFACE(ProjectileManager) COMPONENT(ProjectileManager) INTERFACE(Selectable) COMPONENT(Selectable) INTERFACE(SoundManager) COMPONENT(SoundManager) INTERFACE(Terrain) COMPONENT(Terrain) INTERFACE(UnitMotion) -COMPONENT(UnitMotion) +COMPONENT(UnitMotion) // must be after Obstruction INTERFACE(Visual) COMPONENT(VisualActor) Index: ps/trunk/source/simulation2/components/ICmpFootprint.h =================================================================== --- ps/trunk/source/simulation2/components/ICmpFootprint.h (revision 7483) +++ ps/trunk/source/simulation2/components/ICmpFootprint.h (revision 7484) @@ -1,62 +1,63 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #ifndef INCLUDED_ICMPFOOTPRINT #define INCLUDED_ICMPFOOTPRINT #include "simulation2/system/Interface.h" #include "simulation2/helpers/Position.h" -#include "maths/FixedVector3D.h" + +class CFixedVector3D; /** * Footprints - an approximation of the entity's shape, used for collision detection and for * rendering selection outlines. * A footprint is either a circle (of some radius) or square (of some width and depth (actually * it's a rectangle)), horizontally aligned, extruded to a given height. */ class ICmpFootprint : public IComponent { public: enum EShape { CIRCLE, SQUARE }; /** * Return the shape of this footprint. * Shapes are horizontal circles or squares, extended vertically upwards to make cylinders or boxes. * @param[out] shape either CIRCLE or SQUARE * @param[out] size0 if CIRCLE then radius, else width (size in X axis) * @param[out] size1 if CIRCLE then radius, else depth (size in Z axis) * @param[out] height size in Y axis */ virtual void GetShape(EShape& shape, entity_pos_t& size0, entity_pos_t& size1, entity_pos_t& height) = 0; /** * Pick a sensible position to place a newly-spawned entity near this footprint, * such that it won't be in an invalid (obstructed) location regardless of the spawned unit's * orientation. * @return the X and Z coordinates of the spawn point, with Y = 0; or the special value (-1, -1, -1) if there's no space */ virtual CFixedVector3D PickSpawnPoint(entity_id_t spawned) = 0; DECLARE_INTERFACE_TYPE(Footprint) }; #endif // INCLUDED_ICMPFOOTPRINT Index: ps/trunk/source/simulation2/components/CCmpTerrain.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpTerrain.cpp (revision 7483) +++ ps/trunk/source/simulation2/components/CCmpTerrain.cpp (revision 7484) @@ -1,77 +1,77 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #include "precompiled.h" #include "simulation2/system/Component.h" #include "ICmpTerrain.h" #include "graphics/Terrain.h" class CCmpTerrain : public ICmpTerrain { public: static void ClassInit(CComponentManager& UNUSED(componentManager)) { } DEFAULT_COMPONENT_ALLOCATOR(Terrain) CTerrain* m_Terrain; // not null static std::string GetSchema() { return ""; } virtual void Init(const CSimContext& context, const CParamNode& UNUSED(paramNode)) { m_Terrain = &context.GetTerrain(); } virtual void Deinit(const CSimContext& UNUSED(context)) { } virtual void Serialize(ISerializer& UNUSED(serialize)) { } virtual void Deserialize(const CSimContext& context, const CParamNode& paramNode, IDeserializer& UNUSED(deserialize)) { Init(context, paramNode); } virtual CFixedVector3D CalcNormal(entity_pos_t x, entity_pos_t z) { CFixedVector3D normal; - m_Terrain->CalcNormalFixed((x / CELL_SIZE).ToInt_RoundToZero(), (z / CELL_SIZE).ToInt_RoundToZero(), normal); + m_Terrain->CalcNormalFixed((x / (int)CELL_SIZE).ToInt_RoundToZero(), (z / (int)CELL_SIZE).ToInt_RoundToZero(), normal); return normal; } virtual entity_pos_t GetGroundLevel(entity_pos_t x, entity_pos_t z) { return m_Terrain->GetExactGroundLevelFixed(x, z); } virtual float GetGroundLevel(float x, float z) { return m_Terrain->GetExactGroundLevel(x, z); } }; REGISTER_COMPONENT_TYPE(Terrain) Index: ps/trunk/source/simulation2/components/CCmpObstructionManager.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpObstructionManager.cpp (revision 7483) +++ ps/trunk/source/simulation2/components/CCmpObstructionManager.cpp (revision 7484) @@ -1,394 +1,532 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #include "precompiled.h" #include "simulation2/system/Component.h" #include "ICmpObstructionManager.h" #include "simulation2/MessageTypes.h" +#include "simulation2/helpers/Geometry.h" #include "simulation2/helpers/Render.h" #include "graphics/Overlay.h" #include "graphics/Terrain.h" -#include "maths/FixedVector2D.h" #include "maths/MathUtil.h" #include "ps/Overlay.h" #include "ps/Profile.h" #include "renderer/Scene.h" // Externally, tags are opaque non-zero positive integers. // Internally, they are tagged (by shape) indexes into shape lists. // idx must be non-zero. -#define TAG_IS_CIRCLE(tag) (((tag) & 1) == 0) -#define TAG_IS_SQUARE(tag) (((tag) & 1) == 1) -#define CIRCLE_INDEX_TO_TAG(idx) (((idx) << 1) | 0) -#define SQUARE_INDEX_TO_TAG(idx) (((idx) << 1) | 1) +#define TAG_IS_UNIT(tag) (((tag) & 1) == 0) +#define TAG_IS_STATIC(tag) (((tag) & 1) == 1) +#define UNIT_INDEX_TO_TAG(idx) (((idx) << 1) | 0) +#define STATIC_INDEX_TO_TAG(idx) (((idx) << 1) | 1) #define TAG_TO_INDEX(tag) ((tag) >> 1) /** - * Internal representation of circle shapes + * Internal representation of axis-aligned sometimes-square sometimes-circle shapes for moving units */ -struct Circle +struct UnitShape { - entity_pos_t x, z, r; + entity_pos_t x, z; + entity_pos_t r; // radius of circle, or half width of square + bool moving; // whether it's currently mobile (and should be generally ignored when pathing) }; /** - * Internal representation of square shapes + * Internal representation of arbitrary-rotation static square shapes for buildings */ -struct Square +struct StaticShape { - entity_pos_t x, z; - entity_angle_t a; - entity_pos_t w, h; + entity_pos_t x, z; // world-space coordinates + CFixedVector2D u, v; // orthogonal unit vectors - axes of local coordinate space + entity_pos_t hw, hh; // half width/height in local coordinate space }; class CCmpObstructionManager : public ICmpObstructionManager { public: static void ClassInit(CComponentManager& componentManager) { componentManager.SubscribeToMessageType(MT_RenderSubmit); // for debug overlays } DEFAULT_COMPONENT_ALLOCATOR(ObstructionManager) bool m_DebugOverlayEnabled; bool m_DebugOverlayDirty; std::vector m_DebugOverlayLines; // TODO: using std::map is a bit inefficient; is there a better way to store these? - std::map m_Circles; - std::map m_Squares; - u32 m_CircleNext; // next allocated id - u32 m_SquareNext; + std::map m_UnitShapes; + std::map m_StaticShapes; + u32 m_UnitShapeNext; // next allocated id + u32 m_StaticShapeNext; static std::string GetSchema() { return ""; } virtual void Init(const CSimContext& context, const CParamNode& UNUSED(paramNode)) { m_DebugOverlayEnabled = false; m_DebugOverlayDirty = true; - m_CircleNext = 1; - m_SquareNext = 1; + m_UnitShapeNext = 1; + m_StaticShapeNext = 1; m_DirtyID = 1; // init to 1 so default-initialised grids are considered dirty } virtual void Deinit(const CSimContext& UNUSED(context)) { } virtual void Serialize(ISerializer& serialize) { // TODO: do something here // (Do we need to serialise the obstruction state, or is it fine to regenerate it from // the original entities after deserialisation?) } virtual void Deserialize(const CSimContext& context, const CParamNode& paramNode, IDeserializer& deserialize) { Init(context, paramNode); // TODO } virtual void HandleMessage(const CSimContext& context, const CMessage& msg, bool UNUSED(global)) { switch (msg.GetType()) { case MT_RenderSubmit: { const CMessageRenderSubmit& msgData = static_cast (msg); RenderSubmit(context, msgData.collector); break; } } } - virtual tag_t AddCircle(entity_pos_t x, entity_pos_t z, entity_pos_t r) + virtual tag_t AddUnitShape(entity_pos_t x, entity_pos_t z, entity_pos_t r, bool moving) { - Circle c = { x, z, r }; - size_t id = m_CircleNext++; - m_Circles[id] = c; + UnitShape shape = { x, z, r, moving }; + size_t id = m_UnitShapeNext++; + m_UnitShapes[id] = shape; MakeDirty(); - return CIRCLE_INDEX_TO_TAG(id); + return UNIT_INDEX_TO_TAG(id); } - virtual tag_t AddSquare(entity_pos_t x, entity_pos_t z, entity_angle_t a, entity_pos_t w, entity_pos_t h) + virtual tag_t AddStaticShape(entity_pos_t x, entity_pos_t z, entity_angle_t a, entity_pos_t w, entity_pos_t h) { - Square s = { x, z, a, w, h }; - size_t id = m_SquareNext++; - m_Squares[id] = s; + CFixed_23_8 s, c; + sincos_approx(a, s, c); + CFixedVector2D u(c, -s); + CFixedVector2D v(s, c); + + StaticShape shape = { x, z, u, v, w/2, h/2 }; + size_t id = m_StaticShapeNext++; + m_StaticShapes[id] = shape; MakeDirty(); - return SQUARE_INDEX_TO_TAG(id); + return STATIC_INDEX_TO_TAG(id); } virtual void MoveShape(tag_t tag, entity_pos_t x, entity_pos_t z, entity_angle_t a) { debug_assert(tag); - if (TAG_IS_CIRCLE(tag)) + if (TAG_IS_UNIT(tag)) { - Circle& c = m_Circles[TAG_TO_INDEX(tag)]; - c.x = x; - c.z = z; + UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)]; + shape.x = x; + shape.z = z; } else { - Square& s = m_Squares[TAG_TO_INDEX(tag)]; - s.x = x; - s.z = z; - s.a = a; + CFixed_23_8 s, c; + sincos_approx(a, s, c); + CFixedVector2D u(c, -s); + CFixedVector2D v(s, c); + + StaticShape& shape = m_StaticShapes[TAG_TO_INDEX(tag)]; + shape.x = x; + shape.z = z; + shape.u = u; + shape.v = v; } MakeDirty(); } + virtual void SetUnitMovingFlag(tag_t tag, bool moving) + { + debug_assert(tag && TAG_IS_UNIT(tag)); + + if (TAG_IS_UNIT(tag)) + { + UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)]; + shape.moving = moving; + } + } + virtual void RemoveShape(tag_t tag) { debug_assert(tag); - if (TAG_IS_CIRCLE(tag)) - m_Circles.erase(TAG_TO_INDEX(tag)); + if (TAG_IS_UNIT(tag)) + m_UnitShapes.erase(TAG_TO_INDEX(tag)); else - m_Squares.erase(TAG_TO_INDEX(tag)); + m_StaticShapes.erase(TAG_TO_INDEX(tag)); MakeDirty(); } + virtual ObstructionSquare GetObstruction(tag_t tag) + { + debug_assert(tag); + + if (TAG_IS_UNIT(tag)) + { + UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)]; + CFixedVector2D u(entity_pos_t::FromInt(1), entity_pos_t::Zero()); + CFixedVector2D v(entity_pos_t::Zero(), entity_pos_t::FromInt(1)); + ObstructionSquare o = { shape.x, shape.z, u, v, shape.r, shape.r }; + return o; + } + else + { + StaticShape& shape = m_StaticShapes[TAG_TO_INDEX(tag)]; + ObstructionSquare o = { shape.x, shape.z, shape.u, shape.v, shape.hw, shape.hh }; + return o; + } + } + virtual bool TestLine(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r); - virtual bool TestCircle(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r); - virtual bool TestSquare(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h); + virtual bool TestStaticShape(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h); + virtual bool TestUnitShape(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r); virtual bool Rasterise(Grid& grid); + virtual void GetObstructionsInRange(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, std::vector& squares); + virtual bool FindMostImportantObstruction(entity_pos_t x, entity_pos_t z, entity_pos_t r, ObstructionSquare& square); virtual void SetDebugOverlay(bool enabled) { m_DebugOverlayEnabled = enabled; m_DebugOverlayDirty = true; if (!enabled) m_DebugOverlayLines.clear(); } void RenderSubmit(const CSimContext& context, SceneCollector& collector); private: // To support lazy updates of grid rasterisations of obstruction data, // we maintain a DirtyID here and increment it whenever obstructions change; // if a grid has a lower DirtyID then it needs to be updated. size_t m_DirtyID; /** * Mark all previous Rasterise()d grids as dirty */ void MakeDirty() { ++m_DirtyID; m_DebugOverlayDirty = true; } /** * Test whether a Rasterise()d grid is dirty and needs updating */ template bool IsDirty(const Grid& grid) { return grid.m_DirtyID < m_DirtyID; } }; REGISTER_COMPONENT_TYPE(ObstructionManager) -// Detect intersection between ray (0,0)-L and circle with center M radius r -// (Only counts intersections from the outside to the inside) -static bool IntersectRayCircle(CFixedVector2D l, CFixedVector2D m, entity_pos_t r) -{ - // TODO: this should all be checked and tested etc, it's just a rough first attempt for now... - - // Intersections at (t * l.X - m.X)^2 * (t * l.Y - m.Y) = r^2 - // so solve the quadratic for t: - -#define DOT(u, v) ( ((i64)u.X.GetInternalValue()*(i64)v.X.GetInternalValue()) + ((i64)u.Y.GetInternalValue()*(i64)v.Y.GetInternalValue()) ) - i64 a = DOT(l, l); - if (a == 0) - return false; // avoid divide-by-zero later - i64 b = DOT(l, m)*-2; - i64 c = DOT(m, m) - r.GetInternalValue()*r.GetInternalValue(); - i64 d = b*b - 4*a*c; // TODO: overflow breaks stuff here - if (d < 0) // no solutions - return false; - // Find the time of first intersection (entering the circle) - i64 t2a = (-b - isqrt64(d)); // don't divide by 2a explicitly, to avoid rounding errors - if ((a > 0 && t2a < 0) || (a < 0 && t2a > 0)) // if t2a/2a < 0 then intersection was before the ray - return false; - if (t2a >= 2*a) // intersection was after the ray - return false; -// printf("isct (%f,%f) (%f,%f) %f a=%lld b=%lld c=%lld d=%lld t2a=%lld\n", l.X.ToDouble(), l.Y.ToDouble(), m.X.ToDouble(), m.Y.ToDouble(), r.ToDouble(), a, b, c, d, t2a); - return true; -} - bool CCmpObstructionManager::TestLine(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r) { PROFILE("TestLine"); // TODO: this is all very inefficient, it should use some kind of spatial data structures - // Ray-circle intersections - for (std::map::iterator it = m_Circles.begin(); it != m_Circles.end(); ++it) + for (std::map::iterator it = m_UnitShapes.begin(); it != m_UnitShapes.end(); ++it) { - if (!filter.Allowed(CIRCLE_INDEX_TO_TAG(it->first))) + if (!filter.Allowed(UNIT_INDEX_TO_TAG(it->first), it->second.moving)) continue; - if (IntersectRayCircle(CFixedVector2D(x1 - x0, z1 - z0), CFixedVector2D(it->second.x - x0, it->second.z - z0), it->second.r + r)) - return false; + CFixedVector2D center(it->second.x, it->second.z); + CFixedVector2D halfSize(it->second.r + r, it->second.r + r); + CFixedVector2D u(entity_pos_t::FromInt(1), entity_pos_t::Zero()); + CFixedVector2D v(entity_pos_t::Zero(), entity_pos_t::FromInt(1)); + if (Geometry::TestRaySquare(CFixedVector2D(x0, z0) - center, CFixedVector2D(x1, z1) - center, u, v, halfSize)) + return true; + // If this is slow we could use a specialised TestRayAlignedSquare for axis-aligned squares } - // Ray-square intersections - for (std::map::iterator it = m_Squares.begin(); it != m_Squares.end(); ++it) + for (std::map::iterator it = m_StaticShapes.begin(); it != m_StaticShapes.end(); ++it) { - if (!filter.Allowed(SQUARE_INDEX_TO_TAG(it->first))) + if (!filter.Allowed(STATIC_INDEX_TO_TAG(it->first), false)) continue; - // XXX need some kind of square intersection code - if (IntersectRayCircle(CFixedVector2D(x1 - x0, z1 - z0), CFixedVector2D(it->second.x - x0, it->second.z - z0), it->second.w/2 + r)) - return false; + CFixedVector2D center(it->second.x, it->second.z); + CFixedVector2D halfSize(it->second.hw + r, it->second.hh + r); + if (Geometry::TestRaySquare(CFixedVector2D(x0, z0) - center, CFixedVector2D(x1, z1) - center, it->second.u, it->second.v, halfSize)) + return true; } - return true; + return false; } -bool CCmpObstructionManager::TestCircle(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r) +bool CCmpObstructionManager::TestStaticShape(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h) { - PROFILE("TestCircle"); + PROFILE("TestStaticShape"); + + CFixed_23_8 s, c; + sincos_approx(a, s, c); + CFixedVector2D u(c, -s); + CFixedVector2D v(s, c); + CFixedVector2D center(x, z); + CFixedVector2D halfSize(w/2, h/2); - // Circle-circle intersections - for (std::map::iterator it = m_Circles.begin(); it != m_Circles.end(); ++it) + for (std::map::iterator it = m_UnitShapes.begin(); it != m_UnitShapes.end(); ++it) { - if (!filter.Allowed(CIRCLE_INDEX_TO_TAG(it->first))) + if (!filter.Allowed(UNIT_INDEX_TO_TAG(it->first), it->second.moving)) continue; - if (CFixedVector2D(it->second.x - x, it->second.z - z).Length() <= it->second.r + r) - return false; + CFixedVector2D center1(it->second.x, it->second.z); + + if (Geometry::PointIsInSquare(center1 - center, u, v, CFixedVector2D(halfSize.X + it->second.r, halfSize.Y + it->second.r))) + return true; } - // Circle-square intersections - for (std::map::iterator it = m_Squares.begin(); it != m_Squares.end(); ++it) + for (std::map::iterator it = m_StaticShapes.begin(); it != m_StaticShapes.end(); ++it) { - if (!filter.Allowed(SQUARE_INDEX_TO_TAG(it->first))) + if (!filter.Allowed(STATIC_INDEX_TO_TAG(it->first), false)) continue; - // XXX need some kind of square intersection code - if (CFixedVector2D(it->second.x - x, it->second.z - z).Length() <= it->second.w/2 + r) - return false; + CFixedVector2D center1(it->second.x, it->second.z); + CFixedVector2D halfSize1(it->second.hw, it->second.hh); + if (Geometry::TestSquareSquare(center, u, v, halfSize, center1, it->second.u, it->second.v, halfSize1)) + return true; } - return true; + return false; } -bool CCmpObstructionManager::TestSquare(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h) +bool CCmpObstructionManager::TestUnitShape(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r) { - // XXX need to implement this - return TestCircle(filter, x, z, w/2); + PROFILE("TestUnitShape"); + + CFixedVector2D center(x, z); + + for (std::map::iterator it = m_UnitShapes.begin(); it != m_UnitShapes.end(); ++it) + { + if (!filter.Allowed(UNIT_INDEX_TO_TAG(it->first), it->second.moving)) + continue; + + entity_pos_t r1 = it->second.r; + + if (!(it->second.x + r1 < x - r || it->second.x - r1 > x + r || it->second.z + r1 < z - r || it->second.z - r1 > z + r)) + return true; + } + + for (std::map::iterator it = m_StaticShapes.begin(); it != m_StaticShapes.end(); ++it) + { + if (!filter.Allowed(STATIC_INDEX_TO_TAG(it->first), false)) + continue; + + CFixedVector2D center1(it->second.x, it->second.z); + if (Geometry::PointIsInSquare(center1 - center, it->second.u, it->second.v, CFixedVector2D(it->second.hw + r, it->second.hh + r))) + return true; + } + return false; } /** * Compute the tile indexes on the grid nearest to a given point */ static void NearestTile(entity_pos_t x, entity_pos_t z, u16& i, u16& j, u16 w, u16 h) { - i = clamp((x / CELL_SIZE).ToInt_RoundToZero(), 0, w-1); - j = clamp((z / CELL_SIZE).ToInt_RoundToZero(), 0, h-1); + i = clamp((x / (int)CELL_SIZE).ToInt_RoundToZero(), 0, w-1); + j = clamp((z / (int)CELL_SIZE).ToInt_RoundToZero(), 0, h-1); +} + +/** + * Returns the position of the center of the given tile + */ +static void TileCenter(u16 i, u16 j, entity_pos_t& x, entity_pos_t& z) +{ + x = entity_pos_t::FromInt(i*(int)CELL_SIZE + CELL_SIZE/2); + z = entity_pos_t::FromInt(j*(int)CELL_SIZE + CELL_SIZE/2); } bool CCmpObstructionManager::Rasterise(Grid& grid) { if (!IsDirty(grid)) return false; grid.m_DirtyID = m_DirtyID; // TODO: this is all hopelessly inefficient // What we should perhaps do is have some kind of quadtree storing Shapes so it's // quick to invalidate and update small numbers of tiles grid.reset(); - for (std::map::iterator it = m_Circles.begin(); it != m_Circles.end(); ++it) + for (std::map::iterator it = m_StaticShapes.begin(); it != m_StaticShapes.end(); ++it) { - // TODO: need to handle larger circles (r != 0) - u16 i, j; - NearestTile(it->second.x, it->second.z, i, j, grid.m_W, grid.m_H); - grid.set(i, j, 1); - } + CFixedVector2D center(it->second.x, it->second.z); + + // Since we only count tiles whose centers are inside the square, + // we maybe want to expand the square a bit so we're less likely to think there's + // free space between buildings when there isn't. But this is just a random guess + // and needs to be tweaked until everything works nicely. + entity_pos_t expand = entity_pos_t::FromInt(CELL_SIZE / 2); + + CFixedVector2D halfSize(it->second.hw + expand, it->second.hh + expand); + CFixedVector2D halfBound = Geometry::GetHalfBoundingBox(it->second.u, it->second.v, halfSize); - for (std::map::iterator it = m_Squares.begin(); it != m_Squares.end(); ++it) - { - // TODO: need to handle rotations (a != 0) - entity_pos_t x0 = it->second.x - it->second.w/2; - entity_pos_t z0 = it->second.z - it->second.h/2; - entity_pos_t x1 = it->second.x + it->second.w/2; - entity_pos_t z1 = it->second.z + it->second.h/2; u16 i0, j0, i1, j1; - NearestTile(x0, z0, i0, j0, grid.m_W, grid.m_H); // TODO: should be careful about rounding on edges - NearestTile(x1, z1, i1, j1, grid.m_W, grid.m_H); + NearestTile(center.X - halfBound.X, center.Y - halfBound.Y, i0, j0, grid.m_W, grid.m_H); + NearestTile(center.X + halfBound.X, center.Y + halfBound.Y, i1, j1, grid.m_W, grid.m_H); for (u16 j = j0; j <= j1; ++j) + { for (u16 i = i0; i <= i1; ++i) - grid.set(i, j, 1); + { + entity_pos_t x, z; + TileCenter(i, j, x, z); + if (Geometry::PointIsInSquare(CFixedVector2D(x, z) - center, it->second.u, it->second.v, halfSize)) + grid.set(i, j, 1); + } + } } return true; } +void CCmpObstructionManager::GetObstructionsInRange(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, std::vector& squares) +{ + // TODO: this should be made faster with quadtrees or whatever + PROFILE("GetObstructionsInRange"); + + for (std::map::iterator it = m_UnitShapes.begin(); it != m_UnitShapes.end(); ++it) + { + if (!filter.Allowed(UNIT_INDEX_TO_TAG(it->first), it->second.moving)) + continue; + + entity_pos_t r = it->second.r; + + // Skip this object if it's completely outside the requested range + if (it->second.x + r < x0 || it->second.x - r > x1 || it->second.z + r < z0 || it->second.z - r > z1) + continue; + + CFixedVector2D u(entity_pos_t::FromInt(1), entity_pos_t::Zero()); + CFixedVector2D v(entity_pos_t::Zero(), entity_pos_t::FromInt(1)); + ObstructionSquare s = { it->second.x, it->second.z, u, v, r, r }; + squares.push_back(s); + } + + for (std::map::iterator it = m_StaticShapes.begin(); it != m_StaticShapes.end(); ++it) + { + if (!filter.Allowed(STATIC_INDEX_TO_TAG(it->first), false)) + continue; + + entity_pos_t r = it->second.hw + it->second.hh; // overestimate the max dist of an edge from the center + + // Skip this object if its overestimated bounding box is completely outside the requested range + if (it->second.x + r < x0 || it->second.x - r > x1 || it->second.z + r < z0 || it->second.z - r > z1) + continue; + + // TODO: maybe we should use Geometry::GetHalfBoundingBox to be more precise? + + ObstructionSquare s = { it->second.x, it->second.z, it->second.u, it->second.v, it->second.hw, it->second.hh }; + squares.push_back(s); + } +} + +bool CCmpObstructionManager::FindMostImportantObstruction(entity_pos_t x, entity_pos_t z, entity_pos_t r, ObstructionSquare& square) +{ + std::vector squares; + + CFixedVector2D center(x, z); + + // First look for obstructions that are covering the exact target point + NullObstructionFilter filter; + GetObstructionsInRange(filter, x, z, x, z, squares); + // Building squares are more important but returned last, so check backwards + for (std::vector::reverse_iterator it = squares.rbegin(); it != squares.rend(); ++it) + { + CFixedVector2D halfSize(it->hw, it->hh); + if (Geometry::PointIsInSquare(CFixedVector2D(it->x, it->z) - center, it->u, it->v, halfSize)) + { + square = *it; + return true; + } + } + + // Then look for obstructions that cover the target point when expanded by r + // (i.e. if the target is not inside an object but closer than we can get to it) + + // TODO: actually do that + // (This might matter when you tell a unit to walk too close to the edge of a building) + + return false; +} + void CCmpObstructionManager::RenderSubmit(const CSimContext& context, SceneCollector& collector) { if (!m_DebugOverlayEnabled) return; CColor defaultColour(0, 0, 1, 1); + CColor movingColour(1, 0, 1, 1); // If the shapes have changed, then regenerate all the overlays if (m_DebugOverlayDirty) { m_DebugOverlayLines.clear(); - for (std::map::iterator it = m_Circles.begin(); it != m_Circles.end(); ++it) + for (std::map::iterator it = m_UnitShapes.begin(); it != m_UnitShapes.end(); ++it) { m_DebugOverlayLines.push_back(SOverlayLine()); - m_DebugOverlayLines.back().m_Color = defaultColour; - SimRender::ConstructCircleOnGround(context, it->second.x.ToFloat(), it->second.z.ToFloat(), it->second.r.ToFloat(), m_DebugOverlayLines.back()); + m_DebugOverlayLines.back().m_Color = (it->second.moving ? movingColour : defaultColour); + SimRender::ConstructSquareOnGround(context, it->second.x.ToFloat(), it->second.z.ToFloat(), it->second.r.ToFloat()*2, it->second.r.ToFloat()*2, 0, m_DebugOverlayLines.back()); } - for (std::map::iterator it = m_Squares.begin(); it != m_Squares.end(); ++it) + for (std::map::iterator it = m_StaticShapes.begin(); it != m_StaticShapes.end(); ++it) { m_DebugOverlayLines.push_back(SOverlayLine()); m_DebugOverlayLines.back().m_Color = defaultColour; - SimRender::ConstructSquareOnGround(context, it->second.x.ToFloat(), it->second.z.ToFloat(), it->second.w.ToFloat(), it->second.h.ToFloat(), it->second.a.ToFloat(), m_DebugOverlayLines.back()); + float a = atan2(it->second.v.X.ToFloat(), it->second.v.Y.ToFloat()); + SimRender::ConstructSquareOnGround(context, it->second.x.ToFloat(), it->second.z.ToFloat(), it->second.hw.ToFloat()*2, it->second.hh.ToFloat()*2, a, m_DebugOverlayLines.back()); } m_DebugOverlayDirty = false; } for (size_t i = 0; i < m_DebugOverlayLines.size(); ++i) collector.Submit(&m_DebugOverlayLines[i]); } Index: ps/trunk/source/simulation2/components/CCmpObstruction.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpObstruction.cpp (revision 7483) +++ ps/trunk/source/simulation2/components/CCmpObstruction.cpp (revision 7484) @@ -1,179 +1,228 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #include "precompiled.h" #include "simulation2/system/Component.h" #include "ICmpObstruction.h" -#include "ICmpFootprint.h" #include "ICmpObstructionManager.h" +#include "ICmpPosition.h" #include "simulation2/MessageTypes.h" /** * Obstruction implementation. This keeps the ICmpPathfinder's model of the world updated when the * entities move and die, with shapes derived from ICmpFootprint. */ class CCmpObstruction : public ICmpObstruction { public: static void ClassInit(CComponentManager& componentManager) { componentManager.SubscribeToMessageType(MT_PositionChanged); + componentManager.SubscribeToMessageType(MT_MotionChanged); componentManager.SubscribeToMessageType(MT_Destroy); } DEFAULT_COMPONENT_ALLOCATOR(Obstruction) const CSimContext* m_Context; + // Template state: + + enum { + STATIC, + UNIT + } m_Type; + entity_pos_t m_Size0; // radius or width + entity_pos_t m_Size1; // radius or depth bool m_Active; // whether the obstruction is obstructing or just an inactive placeholder + // Dynamic state: + + bool m_Moving; ICmpObstructionManager::tag_t m_Tag; static std::string GetSchema() { return "" "Causes this entity's footprint to obstruct the motion of other units." + "" + "" + "" + "" + "" + "" + "" + "" + "" + "" + "" + "" + "" + "" + "" "" "" "" "" ""; } virtual void Init(const CSimContext& context, const CParamNode& paramNode) { m_Context = &context; + if (paramNode.GetChild("Unit").IsOk()) + { + m_Type = UNIT; + m_Size0 = m_Size1 = paramNode.GetChild("Unit").GetChild("@radius").ToFixed(); + } + else + { + m_Type = STATIC; + m_Size0 = paramNode.GetChild("Static").GetChild("@width").ToFixed(); + m_Size1 = paramNode.GetChild("Static").GetChild("@depth").ToFixed(); + } + if (paramNode.GetChild("Inactive").IsOk()) m_Active = false; else m_Active = true; m_Tag = 0; + m_Moving = false; } virtual void Deinit(const CSimContext& UNUSED(context)) { } virtual void Serialize(ISerializer& UNUSED(serialize)) { // TODO: Coordinate with CCmpObstructionManager serialisation } virtual void Deserialize(const CSimContext& context, const CParamNode& paramNode, IDeserializer& UNUSED(deserialize)) { Init(context, paramNode); // TODO: Coordinate with CCmpObstructionManager serialisation } virtual void HandleMessage(const CSimContext& context, const CMessage& msg, bool UNUSED(global)) { switch (msg.GetType()) { case MT_PositionChanged: { if (!m_Active) break; const CMessagePositionChanged& data = static_cast (msg); if (!data.inWorld && !m_Tag) break; // nothing needs to change CmpPtr cmpObstructionManager(context, SYSTEM_ENTITY); if (cmpObstructionManager.null()) break; if (data.inWorld && m_Tag) { cmpObstructionManager->MoveShape(m_Tag, data.x, data.z, data.a); } else if (data.inWorld && !m_Tag) { // Need to create a new pathfinder shape: - - CmpPtr cmpFootprint(context, GetEntityId()); - if (cmpFootprint.null()) - break; - - ICmpFootprint::EShape shape; - entity_pos_t size0, size1, height; - cmpFootprint->GetShape(shape, size0, size1, height); - - if (shape == ICmpFootprint::SQUARE) - m_Tag = cmpObstructionManager->AddSquare(data.x, data.z, data.a, size0, size1); + if (m_Type == STATIC) + m_Tag = cmpObstructionManager->AddStaticShape(data.x, data.z, data.a, m_Size0, m_Size1); else - m_Tag = cmpObstructionManager->AddCircle(data.x, data.z, size0); + m_Tag = cmpObstructionManager->AddUnitShape(data.x, data.z, m_Size0, m_Moving); } else if (!data.inWorld && m_Tag) { cmpObstructionManager->RemoveShape(m_Tag); m_Tag = 0; } break; } + case MT_MotionChanged: + { + const CMessageMotionChanged& data = static_cast (msg); + m_Moving = !data.speed.IsZero(); + + if (m_Tag && m_Type == UNIT) + { + CmpPtr cmpObstructionManager(context, SYSTEM_ENTITY); + if (cmpObstructionManager.null()) + break; + cmpObstructionManager->SetUnitMovingFlag(m_Tag, m_Moving); + } + break; + } case MT_Destroy: { if (m_Tag) { CmpPtr cmpObstructionManager(context, SYSTEM_ENTITY); if (cmpObstructionManager.null()) break; cmpObstructionManager->RemoveShape(m_Tag); m_Tag = 0; } break; } } } - virtual bool CheckCollisions() + virtual ICmpObstructionManager::tag_t GetObstruction() { - CmpPtr cmpFootprint(*m_Context, GetEntityId()); - if (cmpFootprint.null()) - return false; + return m_Tag; + } + virtual entity_pos_t GetUnitRadius() + { + if (m_Type == UNIT) + return m_Size0; + else + return entity_pos_t::Zero(); + } + + virtual bool CheckCollisions() + { CmpPtr cmpPosition(*m_Context, GetEntityId()); if (cmpPosition.null()) return false; - ICmpFootprint::EShape shape; - entity_pos_t size0, size1, height; - cmpFootprint->GetShape(shape, size0, size1, height); - CFixedVector3D pos = cmpPosition->GetPosition(); CmpPtr cmpObstructionManager(*m_Context, SYSTEM_ENTITY); SkipTagObstructionFilter filter(m_Tag); // ignore collisions with self - if (shape == ICmpFootprint::SQUARE) - return !cmpObstructionManager->TestSquare(filter, pos.X, pos.Z, cmpPosition->GetRotation().Y, size0, size1); + if (m_Type == STATIC) + return cmpObstructionManager->TestStaticShape(filter, pos.X, pos.Z, cmpPosition->GetRotation().Y, m_Size0, m_Size1); else - return !cmpObstructionManager->TestCircle(filter, pos.X, pos.Z, size0); - + return cmpObstructionManager->TestUnitShape(filter, pos.X, pos.Z, m_Size0); } }; REGISTER_COMPONENT_TYPE(Obstruction) Index: ps/trunk/source/simulation2/components/tests/test_Pathfinder.h =================================================================== --- ps/trunk/source/simulation2/components/tests/test_Pathfinder.h (revision 7483) +++ ps/trunk/source/simulation2/components/tests/test_Pathfinder.h (revision 7484) @@ -1,115 +1,115 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #include "simulation2/system/ComponentTest.h" #include "simulation2/components/ICmpPathfinder.h" #include "graphics/MapReader.h" #include "graphics/Terrain.h" #include "graphics/TextureManager.h" #include "ps/Loader.h" #include "ps/Profile.h" #include "ps/ProfileViewer.h" #include "scripting/ScriptingHost.h" #include "simulation/EntityTemplateCollection.h" #include "simulation2/Simulation2.h" class TestCmpPathfinder : public CxxTest::TestSuite { public: void setUp() { g_UseSimulation2 = true; CXeromyces::Startup(); g_VFS = CreateVfs(20 * MiB); TS_ASSERT_OK(g_VFS->Mount(L"", DataDir()/L"mods/public")); TS_ASSERT_OK(g_VFS->Mount(L"cache/", DataDir()/L"cache")); // Set up loads of stuff that's needed in order to load a map new CTextureManager(); new CProfileViewer(); new CProfileManager(); new ScriptingHost(); new CEntityTemplateCollection(); g_EntityTemplateCollection.LoadTemplates(); } void tearDown() { delete &g_EntityTemplateCollection; delete &g_ScriptingHost; delete &g_Profiler; delete &g_ProfileViewer; delete &g_TexMan; g_VFS.reset(); CXeromyces::Terminate(); g_UseSimulation2 = false; } // disabled by default; run tests with the "-test TestCmpPathfinder" flag to enable void test_performance_DISABLED() { CTerrain terrain; CSimulation2 sim2(NULL, &terrain); sim2.LoadDefaultScripts(); sim2.ResetState(); CMapReader* mapReader = new CMapReader(); // it'll call "delete this" itself LDR_BeginRegistering(); mapReader->LoadMap(L"maps/scenarios/Latium.pmp", &terrain, NULL, NULL, NULL, NULL, NULL, NULL, NULL, &sim2, NULL); LDR_EndRegistering(); TS_ASSERT_OK(LDR_NonprogressiveLoad()); sim2.Update(0); CmpPtr cmp(sim2, SYSTEM_ENTITY); #if 0 entity_pos_t x0 = entity_pos_t::FromInt(10); entity_pos_t z0 = entity_pos_t::FromInt(495); entity_pos_t x1 = entity_pos_t::FromInt(500); entity_pos_t z1 = entity_pos_t::FromInt(495); ICmpPathfinder::Goal goal = { x1, z1, entity_pos_t::FromInt(0), entity_pos_t::FromInt(0) }; ICmpPathfinder::Path path; cmp->ComputePath(x0, z0, goal, path); for (size_t i = 0; i < path.m_Waypoints.size(); ++i) printf("%d: %f %f\n", (int)i, path.m_Waypoints[i].x.ToDouble(), path.m_Waypoints[i].z.ToDouble()); #endif srand(1234); for (size_t j = 0; j < 256; ++j) { entity_pos_t x0 = entity_pos_t::FromInt(rand() % 512); entity_pos_t z0 = entity_pos_t::FromInt(rand() % 512); entity_pos_t x1 = entity_pos_t::FromInt(rand() % 512); entity_pos_t z1 = entity_pos_t::FromInt(rand() % 512); - ICmpPathfinder::Goal goal = { x1, z1, entity_pos_t::FromInt(0), entity_pos_t::FromInt(0) }; + ICmpPathfinder::Goal goal = { ICmpPathfinder::Goal::POINT, x1, z1 }; ICmpPathfinder::Path path; cmp->ComputePath(x0, z0, goal, path); } } }; Index: ps/trunk/source/simulation2/components/ICmpUnitMotion.h =================================================================== --- ps/trunk/source/simulation2/components/ICmpUnitMotion.h (revision 7483) +++ ps/trunk/source/simulation2/components/ICmpUnitMotion.h (revision 7484) @@ -1,44 +1,76 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #ifndef INCLUDED_ICMPUNITMOTION #define INCLUDED_ICMPUNITMOTION #include "simulation2/system/Interface.h" #include "ICmpPosition.h" // for entity_pos_t /** * Motion interface for entities with complex movement capabilities. * (Simpler motion is handled by ICmpMotion instead.) * * Currently this is limited to telling the entity to walk to a point. * Eventually it should support different movement speeds, moving to areas * instead of points, moving as part of a group, moving as part of a formation, * etc. */ class ICmpUnitMotion : public IComponent { public: - virtual void MoveToPoint(entity_pos_t x, entity_pos_t z, entity_pos_t minRadius, entity_pos_t maxRadius) = 0; - + /** + * Attempt to walk to a given point, or as close as possible. + * If the unit cannot move anywhere at all, or if there is some other error, then + * returns false. + * Otherwise, sends a MotionChanged message and returns true; it will send another + * MotionChanged message (with speed 0) once it has reached the target or otherwise + * given up trying to reach it. + */ + virtual bool MoveToPoint(entity_pos_t x, entity_pos_t z) = 0; + + /** + * Determine whether the target is within the given range, using the same measurement + * as MoveToAttackRange. + */ + virtual bool IsInAttackRange(entity_id_t target, entity_pos_t minRange, entity_pos_t maxRange) = 0; + + /** + * Attempt to walk into range of a given target, or as close as possible. + * If the unit is already in range, or cannot move anywhere at all, or if there is + * some other error, then returns false. + * Otherwise, sends a MotionChanged message and returns true; it will send another + * MotionChanged message (with speed 0) once it has reached the target range (such that + * IsInAttackRange should return true) or otherwise given up trying to reach it. + */ + virtual bool MoveToAttackRange(entity_id_t target, entity_pos_t minRange, entity_pos_t maxRange) = 0; + + /** + * Get the default speed that this unit will have when walking. + */ virtual CFixed_23_8 GetSpeed() = 0; + /** + * Toggle the rendering of debug info. + */ + virtual void SetDebugOverlay(bool enabled) = 0; + DECLARE_INTERFACE_TYPE(UnitMotion) }; #endif // INCLUDED_ICMPUNITMOTION Index: ps/trunk/source/simulation2/components/CCmpFootprint.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpFootprint.cpp (revision 7483) +++ ps/trunk/source/simulation2/components/CCmpFootprint.cpp (revision 7484) @@ -1,237 +1,230 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #include "precompiled.h" #include "simulation2/system/Component.h" #include "ICmpFootprint.h" +#include "ICmpObstruction.h" #include "ICmpObstructionManager.h" #include "ICmpPosition.h" #include "simulation2/MessageTypes.h" #include "maths/FixedVector2D.h" class CCmpFootprint : public ICmpFootprint { public: static void ClassInit(CComponentManager& UNUSED(componentManager)) { } DEFAULT_COMPONENT_ALLOCATOR(Footprint) const CSimContext* m_Context; EShape m_Shape; CFixed_23_8 m_Size0; // width/radius CFixed_23_8 m_Size1; // height/radius CFixed_23_8 m_Height; static std::string GetSchema() { return "Approximation of the entity's shape, for collision detection and outline rendering. " "Shapes are flat horizontal squares or circles, extended vertically to a given height." "" "" "0.0" "" "" "" "0.0" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" ""; } virtual void Init(const CSimContext& context, const CParamNode& paramNode) { m_Context = &context; if (paramNode.GetChild("Square").IsOk()) { m_Shape = SQUARE; m_Size0 = paramNode.GetChild("Square").GetChild("@width").ToFixed(); m_Size1 = paramNode.GetChild("Square").GetChild("@depth").ToFixed(); } else if (paramNode.GetChild("Circle").IsOk()) { m_Shape = CIRCLE; m_Size0 = m_Size1 = paramNode.GetChild("Circle").GetChild("@radius").ToFixed(); } else { // Error - pick some default m_Shape = CIRCLE; m_Size0 = m_Size1 = CFixed_23_8::FromInt(1); } m_Height = paramNode.GetChild("Height").ToFixed(); } virtual void Deinit(const CSimContext& UNUSED(context)) { } virtual void Serialize(ISerializer& UNUSED(serialize)) { } virtual void Deserialize(const CSimContext& context, const CParamNode& paramNode, IDeserializer& UNUSED(deserialize)) { Init(context, paramNode); } virtual void GetShape(EShape& shape, CFixed_23_8& size0, CFixed_23_8& size1, CFixed_23_8& height) { shape = m_Shape; size0 = m_Size0; size1 = m_Size1; height = m_Height; } virtual CFixedVector3D PickSpawnPoint(entity_id_t spawned) { + // Try to find a free space around the building's footprint. + // (Note that we use the footprint, not the obstruction shape - this might be a bit dodgy + // because the footprint might be inside the obstruction, but it hopefully gives us a nicer + // shape.) + CFixedVector3D error(CFixed_23_8::FromInt(-1), CFixed_23_8::FromInt(-1), CFixed_23_8::FromInt(-1)); CmpPtr cmpPosition(*m_Context, GetEntityId()); if (cmpPosition.null() || !cmpPosition->IsInWorld()) return error; CmpPtr cmpObstructionManager(*m_Context, SYSTEM_ENTITY); if (cmpObstructionManager.null()) return error; - // Always approximate the spawned entity as a circle, so we're orientation-independent - CFixed_23_8 spawnedRadius; + entity_pos_t spawnedRadius; - CmpPtr cmpSpawnedFootprint(*m_Context, spawned); - if (!cmpSpawnedFootprint.null()) - { - EShape shape; - CFixed_23_8 size0, size1, height; - cmpSpawnedFootprint->GetShape(shape, size0, size1, height); - if (shape == CIRCLE) - spawnedRadius = size0; - else - spawnedRadius = std::max(size0, size1); // safe overapproximation of the correct sqrt((size0/2)^2 + (size1/2)^2) - } - else - { - // No footprint - weird but let's just pretend it's a point - spawnedRadius = CFixed_23_8::FromInt(0); - } + CmpPtr cmpSpawnedObstruction(*m_Context, spawned); + if (!cmpSpawnedObstruction.null()) + spawnedRadius = cmpSpawnedObstruction->GetUnitRadius(); + // else zero // The spawn point should be far enough from this footprint to fit the unit, plus a little gap - CFixed_23_8 clearance = spawnedRadius + CFixed_23_8::FromInt(2); + CFixed_23_8 clearance = spawnedRadius + entity_pos_t::FromInt(2); CFixedVector3D initialPos = cmpPosition->GetPosition(); entity_angle_t initialAngle = cmpPosition->GetRotation().Y; if (m_Shape == CIRCLE) { CFixed_23_8 radius = m_Size0 + clearance; // Try equally-spaced points around the circle, starting from the front and expanding outwards in alternating directions const ssize_t numPoints = 31; for (ssize_t i = 0; i < (numPoints+1)/2; i = (i > 0 ? -i : 1-i)) // [0, +1, -1, +2, -2, ... (np-1)/2, -(np-1)/2] { - entity_angle_t angle = initialAngle + (entity_angle_t::Pi()*2).Multiply(entity_angle_t::FromInt(i)/numPoints); + entity_angle_t angle = initialAngle + (entity_angle_t::Pi()*2).Multiply(entity_angle_t::FromInt(i)/(int)numPoints); CFixed_23_8 s, c; sincos_approx(angle, s, c); CFixedVector3D pos (initialPos.X + s.Multiply(radius), CFixed_23_8::Zero(), initialPos.Z + c.Multiply(radius)); SkipTagObstructionFilter filter(spawned); // ignore collisions with the spawned entity - if (cmpObstructionManager->TestCircle(filter, pos.X, pos.Z, spawnedRadius)) + if (!cmpObstructionManager->TestUnitShape(filter, pos.X, pos.Z, spawnedRadius)) return pos; // this position is okay, so return it } } else { CFixed_23_8 s, c; sincos_approx(initialAngle, s, c); for (size_t edge = 0; edge < 4; ++edge) { // Try equally-spaced points along the edge, starting from the middle and expanding outwards in alternating directions const ssize_t numPoints = 9; // Compute the direction and length of the current edge CFixedVector2D dir; CFixed_23_8 sx, sy; switch (edge) { case 0: dir = CFixedVector2D(c, -s); sx = m_Size0; sy = m_Size1; break; case 1: dir = CFixedVector2D(-s, -c); sx = m_Size1; sy = m_Size0; break; case 2: dir = CFixedVector2D(s, c); sx = m_Size1; sy = m_Size0; break; case 3: dir = CFixedVector2D(-c, s); sx = m_Size0; sy = m_Size1; break; } CFixedVector2D center; center.X = initialPos.X + (-dir.Y).Multiply(sy/2 + clearance); center.Y = initialPos.Z + dir.X.Multiply(sy/2 + clearance); - dir = dir.Multiply((sx + clearance*2) / (numPoints-1)); + dir = dir.Multiply((sx + clearance*2) / (int)(numPoints-1)); for (ssize_t i = 0; i < (numPoints+1)/2; i = (i > 0 ? -i : 1-i)) // [0, +1, -1, +2, -2, ... (np-1)/2, -(np-1)/2] { CFixedVector2D pos (center + dir*i); SkipTagObstructionFilter filter(spawned); // ignore collisions with the spawned entity - if (cmpObstructionManager->TestCircle(filter, pos.X, pos.Y, spawnedRadius)) + if (!cmpObstructionManager->TestUnitShape(filter, pos.X, pos.Y, spawnedRadius)) return CFixedVector3D(pos.X, CFixed_23_8::Zero(), pos.Y); // this position is okay, so return it } } } return error; } }; REGISTER_COMPONENT_TYPE(Footprint) Index: ps/trunk/source/simulation2/components/ICmpFootprint.cpp =================================================================== --- ps/trunk/source/simulation2/components/ICmpFootprint.cpp (revision 7483) +++ ps/trunk/source/simulation2/components/ICmpFootprint.cpp (revision 7484) @@ -1,26 +1,28 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #include "precompiled.h" #include "ICmpFootprint.h" #include "simulation2/system/InterfaceScripted.h" +#include "maths/FixedVector3D.h" + BEGIN_INTERFACE_WRAPPER(Footprint) DEFINE_INTERFACE_METHOD_1("PickSpawnPoint", CFixedVector3D, ICmpFootprint, PickSpawnPoint, entity_id_t) END_INTERFACE_WRAPPER(Footprint) Index: ps/trunk/source/simulation2/components/ICmpPathfinder.h =================================================================== --- ps/trunk/source/simulation2/components/ICmpPathfinder.h (revision 7483) +++ ps/trunk/source/simulation2/components/ICmpPathfinder.h (revision 7484) @@ -1,93 +1,101 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #ifndef INCLUDED_ICMPPATHFINDER #define INCLUDED_ICMPPATHFINDER #include "simulation2/system/Interface.h" #include "simulation2/helpers/Position.h" +#include "maths/FixedVector2D.h" + #include +class IObstructionTestFilter; + /** - * Pathfinder algorithm. + * Pathfinder algorithms. + * + * There are two different modes: a tile-based pathfinder that works over long distances and + * accounts for terrain costs but ignore units, and a 'short' vertex-based pathfinder that + * provides precise paths and avoids other units. * - * The pathfinder itself does not depend on other components. Instead, it contains an abstract - * view of the game world, based a series of collision shapes (circles and squares), which is - * updated by calls from other components (typically CCmpObstruction). + * Both use the same concept of a Goal: either a point, circle or square. + * (If the starting point is inside the goal shape then the path will move outwards + * to reach the shape's outline.) * - * Internally it quantises the shapes onto a grid and computes paths over the grid, but the interface - * does not expose that detail. + * The output is a list of waypoints. */ class ICmpPathfinder : public IComponent { public: struct Goal { - entity_pos_t x, z; - entity_pos_t minRadius, maxRadius; + enum { + POINT, + CIRCLE, + SQUARE + } type; + entity_pos_t x, z; // position of center + CFixedVector2D u, v; // if SQUARE, then orthogonal unit axes + entity_pos_t hw, hh; // if SQUARE, then half width & height; if CIRCLE, then hw is radius }; - /** - * Returned paths are currently represented as a series of waypoints. - * These happen to correspond to the centers of horizontally/vertically adjacent tiles - * along the path, but it's probably best not to rely on that. - */ struct Waypoint { entity_pos_t x, z; - u32 cost; // currently a meaningless number }; /** * Returned path. * Waypoints are in *reverse* order (the earliest is at the back of the list) */ struct Path { std::vector m_Waypoints; }; /** - * Determine whether a unit (of radius r) can move between the given points in a straight line, - * without hitting any obstacles. - * This is based on the exact list of obtruction shapes, not the grid approximation. - * This should be used as a shortcut to avoid using the pathfinding algorithm in simple cases, - * and for more refined movement along the found paths. + * Compute a tile-based path from the given point to the goal, and return the set of waypoints. + * The waypoints correspond to the centers of horizontally/vertically adjacent tiles + * along the path. */ - virtual bool CanMoveStraight(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r, u32& cost) = 0; + virtual void ComputePath(entity_pos_t x0, entity_pos_t z0, const Goal& goal, Path& ret) = 0; /** - * Compute a path between the given points, and return the set of waypoints. + * If the debug overlay is enabled, render the path that will computed by ComputePath. */ - virtual void ComputePath(entity_pos_t x0, entity_pos_t z0, const Goal& goal, Path& ret) = 0; + virtual void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const Goal& goal) = 0; /** - * Compute a path between the given points, and draw the latest such path as a terrain overlay. + * Compute a precise path from the given point to the goal, and return the set of waypoints. + * The path is based on the full set of obstructions that pass the filter, such that + * a unit of radius 'r' will be able to follow the path with no collisions. + * The path is restricted to a box of radius 'range' from the starting point. */ - virtual void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const Goal& goal) = 0; + virtual void ComputeShortPath(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t r, entity_pos_t range, const Goal& goal, Path& ret) = 0; /** * Toggle the storage and rendering of debug info. */ virtual void SetDebugOverlay(bool enabled) = 0; DECLARE_INTERFACE_TYPE(Pathfinder) }; #endif // INCLUDED_ICMPPATHFINDER Index: ps/trunk/source/simulation2/components/CCmpPosition.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpPosition.cpp (revision 7483) +++ ps/trunk/source/simulation2/components/CCmpPosition.cpp (revision 7484) @@ -1,390 +1,385 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #include "precompiled.h" #include "simulation2/system/Component.h" #include "ICmpPosition.h" #include "simulation2/MessageTypes.h" #include "ICmpTerrain.h" #include "graphics/Terrain.h" #include "lib/rand.h" #include "maths/MathUtil.h" #include "maths/Matrix3D.h" #include "maths/Vector3D.h" #include "ps/CLogger.h" /** * Basic ICmpPosition implementation. */ class CCmpPosition : public ICmpPosition { public: static void ClassInit(CComponentManager& componentManager) { componentManager.SubscribeToMessageType(MT_TurnStart); componentManager.SubscribeToMessageType(MT_Interpolate); // TODO: if this component turns out to be a performance issue, it should // be optimised by creating a new PositionStatic component that doesn't subscribe // to messages and doesn't store LastX/LastZ, and that should be used for all // entities that don't move } DEFAULT_COMPONENT_ALLOCATOR(Position) const CSimContext* m_Context; // never NULL (after Init/Deserialize) // Template state: enum { UPRIGHT = 0, PITCH = 1, PITCH_ROLL = 2, } m_AnchorType; entity_pos_t m_YOffset; bool m_Floating; float m_RotYSpeed; // maximum radians per second, used by InterpolatedRotY to follow RotY // Dynamic state: bool m_InWorld; entity_pos_t m_X, m_Z, m_LastX, m_LastZ; // these values contain undefined junk if !InWorld entity_angle_t m_RotX, m_RotY, m_RotZ; float m_InterpolatedRotY; // not serialized - bool m_Dirty; // true if position/rotation has changed since last TurnStart - static std::string GetSchema() { return "Allows this entity to exist at a location (and orientation) in the world, and defines some details of the positioning." "" "upright" "0.0" "false" "" "" "" "upright" "pitch" "pitch-roll" "" "" "" "" "" "" "" ""; } virtual void Init(const CSimContext& context, const CParamNode& paramNode) { m_Context = &context; std::wstring anchor = paramNode.GetChild("Anchor").ToString(); if (anchor == L"pitch") m_AnchorType = PITCH; else if (anchor == L"pitch-roll") m_AnchorType = PITCH_ROLL; else m_AnchorType = UPRIGHT; m_InWorld = false; m_YOffset = paramNode.GetChild("Altitude").ToFixed(); m_Floating = paramNode.GetChild("Floating").ToBool(); m_RotYSpeed = 6.f; // TODO: should get from template m_RotX = m_RotY = m_RotZ = entity_angle_t::FromInt(0); m_InterpolatedRotY = 0; - - m_Dirty = false; } virtual void Deinit(const CSimContext& UNUSED(context)) { } virtual void Serialize(ISerializer& serialize) { serialize.Bool("in world", m_InWorld); if (m_InWorld) { serialize.NumberFixed_Unbounded("x", m_X); serialize.NumberFixed_Unbounded("z", m_Z); serialize.NumberFixed_Unbounded("last x", m_LastX); serialize.NumberFixed_Unbounded("last z", m_LastZ); // TODO: for efficiency, we probably shouldn't actually store the last position - it doesn't // matter if we don't have smooth interpolation after reloading a game } serialize.NumberFixed_Unbounded("rot x", m_RotX); serialize.NumberFixed_Unbounded("rot y", m_RotY); serialize.NumberFixed_Unbounded("rot z", m_RotZ); serialize.NumberFixed_Unbounded("altitude", m_YOffset); - serialize.Bool("dirty", m_Dirty); if (serialize.IsDebug()) { const char* anchor = "???"; switch (m_AnchorType) { case UPRIGHT: anchor = "upright"; break; case PITCH: anchor = "pitch"; break; case PITCH_ROLL: anchor = "pitch-roll"; break; } serialize.StringASCII("anchor", anchor, 0, 16); serialize.Bool("floating", m_Floating); } } virtual void Deserialize(const CSimContext& context, const CParamNode& paramNode, IDeserializer& deserialize) { Init(context, paramNode); deserialize.Bool(m_InWorld); if (m_InWorld) { deserialize.NumberFixed_Unbounded(m_X); deserialize.NumberFixed_Unbounded(m_Z); deserialize.NumberFixed_Unbounded(m_LastX); deserialize.NumberFixed_Unbounded(m_LastZ); } deserialize.NumberFixed_Unbounded(m_RotX); deserialize.NumberFixed_Unbounded(m_RotY); deserialize.NumberFixed_Unbounded(m_RotZ); deserialize.NumberFixed_Unbounded(m_YOffset); - deserialize.Bool(m_Dirty); // TODO: should there be range checks on all these values? m_InterpolatedRotY = m_RotY.ToFloat(); } virtual bool IsInWorld() { return m_InWorld; } virtual void MoveOutOfWorld() { m_InWorld = false; - m_Dirty = true; + AdvertisePositionChanges(); } virtual void MoveTo(entity_pos_t x, entity_pos_t z) { m_X = x; m_Z = z; if (!m_InWorld) { m_InWorld = true; m_LastX = m_X; m_LastZ = m_Z; } - m_Dirty = true; + AdvertisePositionChanges(); } virtual void JumpTo(entity_pos_t x, entity_pos_t z) { m_LastX = m_X = x; m_LastZ = m_Z = z; m_InWorld = true; - m_Dirty = true; + AdvertisePositionChanges(); } virtual void SetHeightOffset(entity_pos_t dy) { m_YOffset = dy; - m_Dirty = true; + AdvertisePositionChanges(); } virtual entity_pos_t GetHeightOffset() { return m_YOffset; } virtual CFixedVector3D GetPosition() { if (!m_InWorld) { LOGERROR(L"CCmpPosition::GetPosition called on entity when IsInWorld is false"); return CFixedVector3D(); } entity_pos_t ground; CmpPtr cmpTerrain(*m_Context, SYSTEM_ENTITY); if (!cmpTerrain.null()) { ground = cmpTerrain->GetGroundLevel(m_X, m_Z); // TODO: do something with m_Floating } // NOTE: most callers don't actually care about Y; if this is a performance // issue then we could add a new method that simply returns X/Z return CFixedVector3D(m_X, ground + m_YOffset, m_Z); } virtual void TurnTo(entity_angle_t y) { m_RotY = y; - m_Dirty = true; + AdvertisePositionChanges(); } virtual void SetYRotation(entity_angle_t y) { m_RotY = y; m_InterpolatedRotY = m_RotY.ToFloat(); - m_Dirty = true; + AdvertisePositionChanges(); } virtual void SetXZRotation(entity_angle_t x, entity_angle_t z) { m_RotX = x; m_RotZ = z; - m_Dirty = true; + AdvertisePositionChanges(); } virtual CFixedVector3D GetRotation() { return CFixedVector3D(m_RotX, m_RotY, m_RotZ); } virtual void GetInterpolatedPosition2D(float frameOffset, float& x, float& z, float& rotY) { if (!m_InWorld) { LOGERROR(L"CCmpPosition::GetInterpolatedPosition2D called on entity when IsInWorld is false"); return; } x = Interpolate(m_LastX.ToFloat(), m_X.ToFloat(), frameOffset); z = Interpolate(m_LastZ.ToFloat(), m_Z.ToFloat(), frameOffset); rotY = m_InterpolatedRotY; } virtual CMatrix3D GetInterpolatedTransform(float frameOffset) { if (!m_InWorld) { LOGERROR(L"CCmpPosition::GetInterpolatedTransform called on entity when IsInWorld is false"); CMatrix3D m; m.SetIdentity(); return m; } float x, z, rotY; GetInterpolatedPosition2D(frameOffset, x, z, rotY); float ground = 0; CmpPtr cmpTerrain(*m_Context, SYSTEM_ENTITY); if (!cmpTerrain.null()) { ground = cmpTerrain->GetGroundLevel(x, z); // TODO: do something with m_Floating } float y = ground + m_YOffset.ToFloat(); // TODO: do something with m_AnchorType CMatrix3D m; CMatrix3D mXZ; float Cos = cosf(rotY); float Sin = sinf(rotY); m.SetIdentity(); m._11 = -Cos; m._13 = -Sin; m._31 = Sin; m._33 = -Cos; mXZ.SetIdentity(); mXZ.SetXRotation(m_RotX.ToFloat()); mXZ.RotateZ(m_RotZ.ToFloat()); // TODO: is this all done in the correct order? mXZ = m * mXZ; mXZ.Translate(CVector3D(x, y, z)); return mXZ; } virtual void HandleMessage(const CSimContext& context, const CMessage& msg, bool UNUSED(global)) { switch (msg.GetType()) { case MT_Interpolate: { const CMessageInterpolate& msgData = static_cast (msg); float rotY = m_RotY.ToFloat(); float delta = rotY - m_InterpolatedRotY; // Wrap delta to -M_PI..M_PI delta = fmod(delta + (float)M_PI, 2*(float)M_PI); // range -2PI..2PI if (delta < 0) delta += 2*(float)M_PI; // range 0..2PI delta -= (float)M_PI; // range -M_PI..M_PI // Clamp to max rate float deltaClamped = clamp(delta, -m_RotYSpeed*msgData.frameTime, +m_RotYSpeed*msgData.frameTime); // Calculate new orientation, in a peculiar way in order to make sure the // result gets close to m_orientation (rather than being n*2*M_PI out) m_InterpolatedRotY = rotY + deltaClamped - delta; break; } case MT_TurnStart: { m_LastX = m_X; m_LastZ = m_Z; - if (m_Dirty) - { - if (m_InWorld) - { - CMessagePositionChanged msg(true, m_X, m_Z, m_RotY); - context.GetComponentManager().PostMessage(GetEntityId(), msg); - } - else - { - CMessagePositionChanged msg(false, entity_pos_t(), entity_pos_t(), entity_angle_t()); - context.GetComponentManager().PostMessage(GetEntityId(), msg); - } - m_Dirty = false; - } break; } } } + +private: + void AdvertisePositionChanges() + { + if (m_InWorld) + { + CMessagePositionChanged msg(true, m_X, m_Z, m_RotY); + m_Context->GetComponentManager().PostMessage(GetEntityId(), msg); + } + else + { + CMessagePositionChanged msg(false, entity_pos_t(), entity_pos_t(), entity_angle_t()); + m_Context->GetComponentManager().PostMessage(GetEntityId(), msg); + } + } }; REGISTER_COMPONENT_TYPE(Position) Index: ps/trunk/source/simulation2/components/CCmpUnitMotion.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpUnitMotion.cpp (revision 7483) +++ ps/trunk/source/simulation2/components/CCmpUnitMotion.cpp (revision 7484) @@ -1,323 +1,880 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #include "precompiled.h" #include "simulation2/system/Component.h" #include "ICmpUnitMotion.h" +#include "ICmpObstruction.h" +#include "ICmpObstructionManager.h" #include "ICmpPosition.h" #include "ICmpPathfinder.h" #include "simulation2/MessageTypes.h" +#include "simulation2/helpers/Geometry.h" +#include "simulation2/helpers/Render.h" + +#include "graphics/Overlay.h" +#include "graphics/Terrain.h" +#include "maths/FixedVector2D.h" +#include "ps/Profile.h" +#include "renderer/Scene.h" + +static const entity_pos_t WAYPOINT_ADVANCE_MIN = entity_pos_t::FromInt(CELL_SIZE*4); +static const entity_pos_t WAYPOINT_ADVANCE_MAX = entity_pos_t::FromInt(CELL_SIZE*8); +static const entity_pos_t SHORT_PATH_SEARCH_RANGE = entity_pos_t::FromInt(CELL_SIZE*12); + +static const CColor OVERLAY_COLOUR_PATH(1, 1, 1, 1); +static const CColor OVERLAY_COLOUR_PATH_ACTIVE(1, 1, 0, 1); +static const CColor OVERLAY_COLOUR_SHORT_PATH(1, 0, 0, 1); class CCmpUnitMotion : public ICmpUnitMotion { public: static void ClassInit(CComponentManager& componentManager) { componentManager.SubscribeToMessageType(MT_Update); + componentManager.SubscribeToMessageType(MT_RenderSubmit); // for debug overlays } DEFAULT_COMPONENT_ALLOCATOR(UnitMotion) const CSimContext* m_Context; + bool m_DebugOverlayEnabled; + std::vector m_DebugOverlayLines; + std::vector m_DebugOverlayShortPathLines; + // Template state: CFixed_23_8 m_Speed; // in units per second + entity_pos_t m_Radius; // Dynamic state: - bool m_HasTarget; - ICmpPathfinder::Path m_Path; + bool m_HasTarget; // whether we currently have valid paths and targets // These values contain undefined junk if !HasTarget: - entity_pos_t m_TargetX, m_TargetZ; // currently-selected waypoint - entity_pos_t m_FinalTargetX, m_FinalTargetZ; // final target center (used to face towards it) + ICmpPathfinder::Path m_Path; + ICmpPathfinder::Path m_ShortPath; + entity_pos_t m_ShortTargetX, m_ShortTargetZ; + ICmpPathfinder::Goal m_FinalGoal; enum { IDLE, WALKING, STOPPING }; int m_State; static std::string GetSchema() { return "Provides the unit with the ability to move around the world by itself." "" "7.0" "" "" "" ""; } virtual void Init(const CSimContext& context, const CParamNode& paramNode) { m_Context = &context; m_HasTarget = false; m_Speed = paramNode.GetChild("WalkSpeed").ToFixed(); + CmpPtr cmpObstruction(context, GetEntityId()); + if (!cmpObstruction.null()) + m_Radius = cmpObstruction->GetUnitRadius(); + m_State = IDLE; + + m_DebugOverlayEnabled = false; } virtual void Deinit(const CSimContext& UNUSED(context)) { } virtual void Serialize(ISerializer& serialize) { serialize.Bool("has target", m_HasTarget); if (m_HasTarget) { // TODO: m_Path - serialize.NumberFixed_Unbounded("target x", m_TargetX); - serialize.NumberFixed_Unbounded("target z", m_TargetZ); // TODO: m_FinalTargetAngle } // TODO: m_State } virtual void Deserialize(const CSimContext& context, const CParamNode& paramNode, IDeserializer& deserialize) { Init(context, paramNode); deserialize.Bool(m_HasTarget); if (m_HasTarget) { - deserialize.NumberFixed_Unbounded(m_TargetX); - deserialize.NumberFixed_Unbounded(m_TargetZ); } } virtual void HandleMessage(const CSimContext& context, const CMessage& msg, bool UNUSED(global)) { switch (msg.GetType()) { case MT_Update: { CFixed_23_8 dt = static_cast (msg).turnLength; if (m_State == STOPPING) { m_State = IDLE; CMessageMotionChanged msg(CFixed_23_8::FromInt(0)); context.GetComponentManager().PostMessage(GetEntityId(), msg); } Move(context, dt); break; } + case MT_RenderSubmit: + { + const CMessageRenderSubmit& msgData = static_cast (msg); + RenderSubmit(context, msgData.collector); + break; + } } } - void SwitchState(const CSimContext& context, int state) + virtual CFixed_23_8 GetSpeed() { - debug_assert(state == IDLE || state == WALKING); + return m_Speed; + } - // IDLE -> IDLE -- no change - // IDLE -> WALKING -- send a MotionChanged message - // WALKING -> IDLE -- set to STOPPING, so we'll send MotionChanged in the next Update - // WALKING -> WALKING -- no change - // STOPPING -> IDLE -- stay in STOPPING - // STOPPING -> WALKING -- set to WALKING, send no messages - - if (m_State == IDLE && state == WALKING) - { - CMessageMotionChanged msg(m_Speed); - context.GetComponentManager().PostMessage(GetEntityId(), msg); - m_State = WALKING; - return; + virtual void SetDebugOverlay(bool enabled) + { + m_DebugOverlayEnabled = enabled; + if (enabled) + { + RenderPath(*m_Context, m_Path, m_DebugOverlayLines, OVERLAY_COLOUR_PATH); + RenderPath(*m_Context, m_ShortPath, m_DebugOverlayShortPathLines, OVERLAY_COLOUR_SHORT_PATH); } + } - if (m_State == WALKING && state == IDLE) + virtual bool MoveToPoint(entity_pos_t x, entity_pos_t z); + virtual bool MoveToAttackRange(entity_id_t target, entity_pos_t minRange, entity_pos_t maxRange); + virtual bool IsInAttackRange(entity_id_t target, entity_pos_t minRange, entity_pos_t maxRange); + +private: + /** + * Check whether moving from pos to target is safe (won't hit anything). + * If safe, returns true (the caller should do cmpPosition->MoveTo). + * Otherwise returns false, and either computes a new path to use on the + * next turn or makes the unit stop. + */ + bool CheckMovement(CFixedVector2D pos, CFixedVector2D target); + + /** + * Do the per-turn movement and other updates + */ + void Move(const CSimContext& context, CFixed_23_8 dt); + + void StopAndFaceGoal(CFixedVector2D pos); + + /** + * Rotate to face towards the target point, given the current pos + */ + void FaceTowardsPoint(CFixedVector2D pos, entity_pos_t x, entity_pos_t z); + + /** + * Change between idle/walking states; automatically sends MotionChanged messages when appropriate + */ + void SwitchState(const CSimContext& context, int state); + + bool ShouldTreatTargetAsCircle(entity_pos_t range, entity_pos_t hw, entity_pos_t hh, entity_pos_t circleRadius); + + /** + * Recompute the whole path to the current goal. + * Returns false on error or if the unit can't move anywhere at all. + */ + bool RegeneratePath(CFixedVector2D pos, bool avoidMovingUnits); + + /** + * Maybe select a new long waypoint if we're getting too close to the + * current one. + */ + void MaybePickNextWaypoint(const CFixedVector2D& pos); + + /** + * Select a next long waypoint, given the current unit position. + * Also recomputes the short path to use that waypoint. + * Returns false on error, or if there is no waypoint to pick. + */ + bool PickNextWaypoint(const CFixedVector2D& pos, bool avoidMovingUnits); + + /** + * Select a new short waypoint as the current target, + * which possibly involves first selecting a new long waypoint. + * Returns false on error, or if there is no waypoint to pick. + */ + bool PickNextShortWaypoint(const CFixedVector2D& pos, bool avoidMovingUnits); + + /** + * Convert a path into a renderable list of lines + */ + void RenderPath(const CSimContext& context, const ICmpPathfinder::Path& path, std::vector& lines, CColor color); + + void RenderSubmit(const CSimContext& context, SceneCollector& collector); +}; + +REGISTER_COMPONENT_TYPE(UnitMotion) + +bool CCmpUnitMotion::CheckMovement(CFixedVector2D pos, CFixedVector2D target) +{ + CmpPtr cmpObstructionManager(*m_Context, SYSTEM_ENTITY); + if (cmpObstructionManager.null()) + return false; + + NullObstructionFilter filter; + + entity_pos_t delta = entity_pos_t::FromInt(1) / 8; + // add a small delta so that we don't get so close that the pathfinder thinks + // we've actually crossed the edge (given minor numerical inaccuracies) + // TODO: keep this in sync with CCmpPathfinder::ComputeShortPath delta + // (this value needs to be smaller) + // TODO: work out what this value should actually be, rather than just guessing + + if (cmpObstructionManager->TestLine(filter, pos.X, pos.Y, target.X, target.Y, m_Radius + delta)) + { + // Oops, hit something + // TODO: we ought to wait for obstructions to move away instead of immediately throwing away the whole path + // TODO: actually a whole proper collision resolution thing needs to be designed and written + if (!RegeneratePath(pos, true)) { - m_State = STOPPING; - return; + // Oh dear, we can't find the path any more; give up + StopAndFaceGoal(pos); + return false; } + // Wait for the next Update before we try moving again + return false; + } + + return true; +} + +void CCmpUnitMotion::Move(const CSimContext& context, CFixed_23_8 dt) +{ + PROFILE("Move"); + + if (!m_HasTarget) + return; + + CmpPtr cmpPosition(context, GetEntityId()); + if (cmpPosition.null()) + return; + + CFixedVector3D pos3 = cmpPosition->GetPosition(); + CFixedVector2D pos (pos3.X, pos3.Z); - if (m_State == STOPPING && state == IDLE) + // We want to move (at most) m_Speed*dt units from pos towards the next waypoint + + while (dt > CFixed_23_8::FromInt(0)) + { + CFixedVector2D target(m_ShortTargetX, m_ShortTargetZ); + CFixedVector2D offset = target - pos; + + // Face towards the target + entity_angle_t angle = atan2_approx(offset.X, offset.Y); + cmpPosition->TurnTo(angle); + + // Work out how far we can travel in dt + CFixed_23_8 maxdist = m_Speed.Multiply(dt); + + // If the target is close, we can move there directly + CFixed_23_8 offsetLength = offset.Length(); + if (offsetLength <= maxdist) { + if (!CheckMovement(pos, target)) + return; + + pos = target; + cmpPosition->MoveTo(pos.X, pos.Y); + + // Spend the rest of the time heading towards the next waypoint + dt = dt - (offset.Length() / m_Speed); + MaybePickNextWaypoint(pos); + if (PickNextShortWaypoint(pos, false)) + continue; + + // We ran out of usable waypoints, so stop now + StopAndFaceGoal(pos); return; } - - if (m_State == STOPPING && state == WALKING) + else { - m_State = WALKING; + // Not close enough, so just move in the right direction + offset.Normalize(maxdist); + target = pos + offset; + + if (!CheckMovement(pos, target)) + return; + + pos = target; + cmpPosition->MoveTo(pos.X, pos.Y); + + MaybePickNextWaypoint(pos); + return; } } +} + +void CCmpUnitMotion::StopAndFaceGoal(CFixedVector2D pos) +{ + SwitchState(*m_Context, IDLE); + FaceTowardsPoint(pos, m_FinalGoal.x, m_FinalGoal.z); + + // TODO: if the goal was a square building, we ought to point towards the + // nearest point on the square, not towards its center +} - virtual void MoveToPoint(entity_pos_t x, entity_pos_t z, entity_pos_t minRadius, entity_pos_t maxRadius) +void CCmpUnitMotion::FaceTowardsPoint(CFixedVector2D pos, entity_pos_t x, entity_pos_t z) +{ + CFixedVector2D target(x, z); + CFixedVector2D offset = target - pos; + if (!offset.IsZero()) { - CmpPtr cmpPathfinder (*m_Context, SYSTEM_ENTITY); - if (cmpPathfinder.null()) - return; + entity_angle_t angle = atan2_approx(offset.X, offset.Y); CmpPtr cmpPosition(*m_Context, GetEntityId()); if (cmpPosition.null()) return; + cmpPosition->TurnTo(angle); + } +} - SwitchState(*m_Context, WALKING); +void CCmpUnitMotion::SwitchState(const CSimContext& context, int state) +{ + debug_assert(state == IDLE || state == WALKING); - CFixedVector3D pos = cmpPosition->GetPosition(); + if (state == IDLE) + m_HasTarget = false; - m_Path.m_Waypoints.clear(); + // IDLE -> IDLE -- no change + // IDLE -> WALKING -- send a MotionChanged(speed) message + // WALKING -> IDLE -- set to STOPPING, so we'll send MotionChanged(0) in the next Update + // WALKING -> WALKING -- send a MotionChanged(speed) message + // STOPPING -> IDLE -- stay in STOPPING + // STOPPING -> WALKING -- set to WALKING, send MotionChanged(speed) -// u32 cost; -// entity_pos_t r = entity_pos_t::FromInt(0); // TODO: should get this from the entity's size -// if (cmpPathfinder->CanMoveStraight(pos.X, pos.Z, x, z, r, cost)) -// { -// m_TargetX = x; -// m_TargetZ = z; -// m_HasTarget = true; -// } -// else - { - ICmpPathfinder::Goal goal; - goal.x = x; - goal.z = z; - goal.minRadius = minRadius; - goal.maxRadius = maxRadius; - cmpPathfinder->SetDebugPath(pos.X, pos.Z, goal); - cmpPathfinder->ComputePath(pos.X, pos.Z, goal, m_Path); + if (state == WALKING) + { + CMessageMotionChanged msg(m_Speed); + context.GetComponentManager().PostMessage(GetEntityId(), msg); + } - // If there's no waypoints then we've stopped already, otherwise move to the first one - if (m_Path.m_Waypoints.empty()) - { - m_HasTarget = false; - SwitchState(*m_Context, IDLE); - } - else - { - m_FinalTargetX = x; - m_FinalTargetZ = z; - PickNextWaypoint(pos); - } - } + if (m_State == IDLE && state == WALKING) + { + m_State = WALKING; + return; } - virtual CFixed_23_8 GetSpeed() + if (m_State == WALKING && state == IDLE) { - return m_Speed; + m_State = STOPPING; + return; } - void Move(const CSimContext& context, CFixed_23_8 dt); + if (m_State == STOPPING && state == IDLE) + { + return; + } - void PickNextWaypoint(const CFixedVector3D& pos); -}; + if (m_State == STOPPING && state == WALKING) + { + m_State = WALKING; + return; + } +} -REGISTER_COMPONENT_TYPE(UnitMotion) +bool CCmpUnitMotion::MoveToPoint(entity_pos_t x, entity_pos_t z) +{ + PROFILE("MoveToPoint"); + CmpPtr cmpPosition(*m_Context, GetEntityId()); + if (cmpPosition.null() || !cmpPosition->IsInWorld()) + return false; -void CCmpUnitMotion::Move(const CSimContext& context, CFixed_23_8 dt) -{ - if (!m_HasTarget) - return; + CFixedVector3D pos3 = cmpPosition->GetPosition(); + CFixedVector2D pos (pos3.X, pos3.Z); - CmpPtr cmpPosition(context, GetEntityId()); - if (cmpPosition.null()) - return; + // Reset any current movement + m_HasTarget = false; - CFixedVector3D pos = cmpPosition->GetPosition(); - pos.Y = CFixed_23_8::FromInt(0); // remove Y so it doesn't influence our distance calculations + ICmpPathfinder::Goal goal; - // We want to move (at most) m_Speed*dt units from pos towards the next waypoint + CmpPtr cmpObstructionManager(*m_Context, SYSTEM_ENTITY); + if (cmpObstructionManager.null()) + return false; - while (dt > CFixed_23_8::FromInt(0)) + ICmpObstructionManager::ObstructionSquare obstruction; + if (cmpObstructionManager->FindMostImportantObstruction(x, z, m_Radius, obstruction)) { - CFixedVector3D target(m_TargetX, CFixed_23_8::FromInt(0), m_TargetZ); - CFixedVector3D offset = target - pos; + // If we're aiming inside a building, then aim for the outline of the building instead + // TODO: if we're aiming at a unit then maybe a circle would look nicer? - // Face towards the target - entity_angle_t angle = atan2_approx(offset.X, offset.Z); - cmpPosition->TurnTo(angle); + goal.type = ICmpPathfinder::Goal::SQUARE; + goal.x = obstruction.x; + goal.z = obstruction.z; + goal.u = obstruction.u; + goal.v = obstruction.v; + entity_pos_t delta = entity_pos_t::FromInt(1) / 4; // nudge the goal outwards so it doesn't intersect the building itself + goal.hw = obstruction.hw + m_Radius + delta; + goal.hh = obstruction.hh + m_Radius + delta; + } + else + { + // Unobstructed - head directly for the goal + goal.type = ICmpPathfinder::Goal::POINT; + goal.x = x; + goal.z = z; + } - // Work out how far we can travel in dt - CFixed_23_8 maxdist = m_Speed.Multiply(dt); - // If the target is close, we can move there directly - if (offset.Length() <= maxdist) + m_FinalGoal = goal; + if (!RegeneratePath(pos, false)) + return false; + + SwitchState(*m_Context, WALKING); + return true; +} + +bool CCmpUnitMotion::ShouldTreatTargetAsCircle(entity_pos_t range, entity_pos_t hw, entity_pos_t hh, entity_pos_t circleRadius) +{ + // Given a square, plus a target range we should reach, the shape at that distance + // is a round-cornered square which we can approximate as either a circle or as a square. + // Choose the shape that will minimise the worst-case error: + + // For a square, error is (sqrt(2)-1) * range at the corners + entity_pos_t errSquare = (entity_pos_t::FromInt(4142)/10000).Multiply(range); + + // For a circle, error is radius-hw at the sides and radius-hh at the top/bottom + entity_pos_t errCircle = circleRadius - std::min(hw, hh); + + return (errCircle < errSquare); +} + +bool CCmpUnitMotion::MoveToAttackRange(entity_id_t target, entity_pos_t minRange, entity_pos_t maxRange) +{ + PROFILE("MoveToAttackRange"); + + CmpPtr cmpPosition(*m_Context, GetEntityId()); + if (cmpPosition.null() || !cmpPosition->IsInWorld()) + return false; + + CFixedVector3D pos3 = cmpPosition->GetPosition(); + CFixedVector2D pos (pos3.X, pos3.Z); + + // Reset any current movement + m_HasTarget = false; + + ICmpPathfinder::Goal goal; + + CmpPtr cmpObstructionManager(*m_Context, SYSTEM_ENTITY); + if (cmpObstructionManager.null()) + return false; + + ICmpObstructionManager::tag_t tag = 0; + + CmpPtr cmpObstruction(*m_Context, target); + if (!cmpObstruction.null()) + tag = cmpObstruction->GetObstruction(); + + /* + * If we're starting outside the maxRange, we need to move closer in. + * If we're starting inside the minRange, we need to move further out. + * These ranges are measured from the center of this entity to the edge of the target; + * we add the goal range onto the size of the target shape to get the goal shape. + * (Then we extend it outwards/inwards by a little bit to be sure we'll end up + * within the right range, in case of minor numerical inaccuracies.) + * + * There's a bit of a problem with large square targets: + * the pathfinder only lets us move to goals that are squares, but the points an equal + * distance from the target make a rounded square shape instead. + * + * When moving closer, we could shrink the goal radius to 1/sqrt(2) so the goal shape fits entirely + * within the desired rounded square, but that gives an unfair advantage to attackers who approach + * the target diagonally. + * + * If the target is small relative to the range (e.g. archers attacking anything), + * then we cheat and pretend the target is actually a circle. + * (TODO: that probably looks rubbish for things like walls?) + * + * If the target is large relative to the range (e.g. melee units attacking buildings), + * then we multiply maxRange by approx 1/sqrt(2) to guarantee they'll always aim close enough. + * (Those units should set minRange to 0 so they'll never be considered *too* close.) + */ + + const entity_pos_t goalDelta = entity_pos_t::FromInt(CELL_SIZE)/4; // for extending the goal outwards/inwards a little bit + + if (tag) + { + ICmpObstructionManager::ObstructionSquare obstruction = cmpObstructionManager->GetObstruction(tag); + + CFixedVector2D halfSize(obstruction.hw, obstruction.hh); + goal.x = obstruction.x; + goal.z = obstruction.z; + + entity_pos_t distance = Geometry::DistanceToSquare(pos - CFixedVector2D(obstruction.x, obstruction.z), obstruction.u, obstruction.v, halfSize); + + if (distance < minRange) + { + // Too close to the square - need to move away + + entity_pos_t goalDistance = minRange + goalDelta; + + goal.type = ICmpPathfinder::Goal::SQUARE; + goal.u = obstruction.u; + goal.v = obstruction.v; + entity_pos_t delta = std::max(goalDistance, m_Radius + entity_pos_t::FromInt(CELL_SIZE)/16); // ensure it's far enough to not intersect the building itself + goal.hw = obstruction.hw + delta; + goal.hh = obstruction.hh + delta; + } + else if (distance < maxRange) + { + // We're already in range - no need to move anywhere + FaceTowardsPoint(pos, goal.x, goal.z); + return false; + } + else { - // If we've reached the last waypoint, stop - if (m_Path.m_Waypoints.empty()) + // We might need to move closer: + + // Circumscribe the square + entity_pos_t circleRadius = halfSize.Length(); + + if (ShouldTreatTargetAsCircle(maxRange, obstruction.hw, obstruction.hh, circleRadius)) { - cmpPosition->MoveTo(target.X, target.Z); + // The target is small relative to our range, so pretend it's a circle + + // Note that the distance to the circle will always be less than + // the distance to the square, so the previous "distance < maxRange" + // check is still valid (though not sufficient) + entity_pos_t circleDistance = (pos - CFixedVector2D(obstruction.x, obstruction.z)).Length() - circleRadius; - // If we didn't reach the final goal, point towards it now - if (target.X != m_FinalTargetX || target.Z != m_FinalTargetZ) + if (circleDistance < maxRange) { - CFixedVector3D final(m_FinalTargetX, CFixed_23_8::FromInt(0), m_FinalTargetZ); - CFixedVector3D finalOffset = final - target; - entity_angle_t angle = atan2_approx(finalOffset.X, finalOffset.Z); - cmpPosition->TurnTo(angle); + // We're already in range - no need to move anywhere + FaceTowardsPoint(pos, goal.x, goal.z); + return false; } - m_HasTarget = false; - SwitchState(context, IDLE); - return; + entity_pos_t goalDistance = maxRange - goalDelta; + + goal.type = ICmpPathfinder::Goal::CIRCLE; + goal.hw = circleRadius + goalDistance; } + else + { + // The target is large relative to our range, so treat it as a square and + // get close enough that the diagonals come within range - // Otherwise, spend the rest of the time heading towards the next waypoint - dt = dt - (offset.Length() / m_Speed); - pos = target; - PickNextWaypoint(pos); - continue; + entity_pos_t goalDistance = (maxRange - goalDelta)*2 / 3; // multiply by slightly less than 1/sqrt(2) + + goal.type = ICmpPathfinder::Goal::SQUARE; + goal.u = obstruction.u; + goal.v = obstruction.v; + entity_pos_t delta = std::max(goalDistance, m_Radius + entity_pos_t::FromInt(CELL_SIZE)/16); // ensure it's far enough to not intersect the building itself + goal.hw = obstruction.hw + delta; + goal.hh = obstruction.hh + delta; + } + } + } + else + { + // The target didn't have an obstruction or obstruction shape, so treat it as a point instead + + CmpPtr cmpTargetPosition(*m_Context, target); + if (cmpTargetPosition.null() || !cmpTargetPosition->IsInWorld()) + return false; + + CFixedVector3D targetPos = cmpTargetPosition->GetPosition(); + + entity_pos_t distance = (pos - CFixedVector2D(targetPos.X, targetPos.Z)).Length(); + + entity_pos_t goalDistance; + if (distance < minRange) + { + goalDistance = minRange + goalDelta; + } + else if (distance > maxRange) + { + goalDistance = maxRange - goalDelta; } else { - // Not close enough, so just move in the right direction - offset.Normalize(maxdist); - pos += offset; - cmpPosition->MoveTo(pos.X, pos.Z); - return; + // We're already in range - no need to move anywhere + FaceTowardsPoint(pos, goal.x, goal.z); + return false; } + + // TODO: what happens if goalDistance < 0? (i.e. we probably can never get close enough to the target) + + goal.type = ICmpPathfinder::Goal::CIRCLE; + goal.x = targetPos.X; + goal.z = targetPos.Z; + goal.hw = m_Radius + goalDistance; } + + m_FinalGoal = goal; + if (!RegeneratePath(pos, false)) + return false; + + SwitchState(*m_Context, WALKING); + return true; } -void CCmpUnitMotion::PickNextWaypoint(const CFixedVector3D& pos) +bool CCmpUnitMotion::IsInAttackRange(entity_id_t target, entity_pos_t minRange, entity_pos_t maxRange) { - // We can always pick the immediate next waypoint - debug_assert(!m_Path.m_Waypoints.empty()); - m_TargetX = m_Path.m_Waypoints.back().x; - m_TargetZ = m_Path.m_Waypoints.back().z; - m_Path.m_Waypoints.pop_back(); - m_HasTarget = true; + // This function closely mirrors MoveToAttackRange - it needs to return true + // after that Move has completed + + CmpPtr cmpPosition(*m_Context, GetEntityId()); + if (cmpPosition.null() || !cmpPosition->IsInWorld()) + return false; + + CFixedVector3D pos3 = cmpPosition->GetPosition(); + CFixedVector2D pos (pos3.X, pos3.Z); + + CmpPtr cmpObstructionManager(*m_Context, SYSTEM_ENTITY); + if (cmpObstructionManager.null()) + return false; + + ICmpObstructionManager::tag_t tag = 0; + + CmpPtr cmpObstruction(*m_Context, target); + if (!cmpObstruction.null()) + tag = cmpObstruction->GetObstruction(); - // To smooth the motion and avoid grid-constrained motion, we could try picking some - // subsequent waypoints instead, if we can reach them without hitting any obstacles + entity_pos_t distance; + if (tag) + { + ICmpObstructionManager::ObstructionSquare obstruction = cmpObstructionManager->GetObstruction(tag); + + CFixedVector2D halfSize(obstruction.hw, obstruction.hh); + entity_pos_t distance = Geometry::DistanceToSquare(pos - CFixedVector2D(obstruction.x, obstruction.z), obstruction.u, obstruction.v, halfSize); + + // See if we're too close to the target square + if (distance < minRange) + return false; + + // See if we're close enough to the target square + if (distance <= maxRange) + return true; + + entity_pos_t circleRadius = halfSize.Length(); + + if (ShouldTreatTargetAsCircle(maxRange, obstruction.hw, obstruction.hh, circleRadius)) + { + // The target is small relative to our range, so pretend it's a circle + // and see if we're close enough to that + + entity_pos_t circleDistance = (pos - CFixedVector2D(obstruction.x, obstruction.z)).Length() - circleRadius; + + if (circleDistance <= maxRange) + return true; + } + + return false; + } + else + { + CmpPtr cmpTargetPosition(*m_Context, target); + if (cmpTargetPosition.null() || !cmpTargetPosition->IsInWorld()) + return false; + + CFixedVector3D targetPos = cmpTargetPosition->GetPosition(); + + entity_pos_t distance = (pos - CFixedVector2D(targetPos.X, targetPos.Z)).Length(); + + if (minRange <= distance && distance <= maxRange) + return true; + + return false; + } +} + +bool CCmpUnitMotion::RegeneratePath(CFixedVector2D pos, bool avoidMovingUnits) +{ CmpPtr cmpPathfinder (*m_Context, SYSTEM_ENTITY); if (cmpPathfinder.null()) + return false; + + m_Path.m_Waypoints.clear(); + m_ShortPath.m_Waypoints.clear(); + + // TODO: if it's close then just do a short path, not a long path + cmpPathfinder->SetDebugPath(pos.X, pos.Y, m_FinalGoal); + cmpPathfinder->ComputePath(pos.X, pos.Y, m_FinalGoal, m_Path); + + if (m_DebugOverlayEnabled) + RenderPath(*m_Context, m_Path, m_DebugOverlayLines, OVERLAY_COLOUR_PATH); + + // If there's no waypoints then we've stopped already, otherwise move to the first one + if (m_Path.m_Waypoints.empty()) + { + m_HasTarget = false; + return false; + } + else + { + return PickNextShortWaypoint(pos, avoidMovingUnits); + } +} + +void CCmpUnitMotion::MaybePickNextWaypoint(const CFixedVector2D& pos) +{ + if (m_Path.m_Waypoints.empty()) return; - for (size_t i = 0; i < 3 && !m_Path.m_Waypoints.empty(); ++i) + CFixedVector2D w(m_Path.m_Waypoints.back().x, m_Path.m_Waypoints.back().z); + if ((w - pos).Length() < WAYPOINT_ADVANCE_MIN) + PickNextWaypoint(pos, false); // TODO: handle failures? +} + +bool CCmpUnitMotion::PickNextWaypoint(const CFixedVector2D& pos, bool avoidMovingUnits) +{ + if (m_Path.m_Waypoints.empty()) + return false; + + // First try to get the immediate next waypoint + entity_pos_t targetX = m_Path.m_Waypoints.back().x; + entity_pos_t targetZ = m_Path.m_Waypoints.back().z; + m_Path.m_Waypoints.pop_back(); + + // To smooth the motion and avoid grid-constrained movement and allow dynamic obstacle avoidance, + // try skipping some more waypoints if they're close enough + + while (!m_Path.m_Waypoints.empty()) { - u32 cost; - entity_pos_t r = entity_pos_t::FromInt(0); // TODO: should get this from the entity's size - if (!cmpPathfinder->CanMoveStraight(pos.X, pos.Z, m_Path.m_Waypoints.back().x, m_Path.m_Waypoints.back().z, r, cost)) + CFixedVector2D w(m_Path.m_Waypoints.back().x, m_Path.m_Waypoints.back().z); + if ((w - pos).Length() > WAYPOINT_ADVANCE_MAX) break; - m_TargetX = m_Path.m_Waypoints.back().x; - m_TargetZ = m_Path.m_Waypoints.back().z; + targetX = m_Path.m_Waypoints.back().x; + targetZ = m_Path.m_Waypoints.back().z; m_Path.m_Waypoints.pop_back(); } + + // Highlight the targeted waypoint + if (m_DebugOverlayEnabled) + m_DebugOverlayLines[m_Path.m_Waypoints.size()].m_Color = OVERLAY_COLOUR_PATH_ACTIVE; + + // Now we need to recompute a short path to the waypoint + m_ShortPath.m_Waypoints.clear(); + + ICmpPathfinder::Goal goal; + if (m_Path.m_Waypoints.empty()) + { + // This was the last waypoint - head for the exact goal + goal = m_FinalGoal; + } + else + { + // Head for somewhere near the waypoint (but allow some leeway in case it's obstructed) + goal.type = ICmpPathfinder::Goal::CIRCLE; + goal.hw = entity_pos_t::FromInt(CELL_SIZE*3/2); + goal.x = targetX; + goal.z = targetZ; + } + + CmpPtr cmpPathfinder (*m_Context, SYSTEM_ENTITY); + if (cmpPathfinder.null()) + return false; + + // Set up the filter to avoid/ignore moving units + NullObstructionFilter filterNull; + StationaryObstructionFilter filterStationary; + const IObstructionTestFilter* filter; + if (avoidMovingUnits) + filter = &filterNull; + else + filter = &filterStationary; + + cmpPathfinder->ComputeShortPath(*filter, pos.X, pos.Y, m_Radius, SHORT_PATH_SEARCH_RANGE, goal, m_ShortPath); + + if (m_DebugOverlayEnabled) + RenderPath(*m_Context, m_ShortPath, m_DebugOverlayShortPathLines, OVERLAY_COLOUR_SHORT_PATH); + + return true; +} + +bool CCmpUnitMotion::PickNextShortWaypoint(const CFixedVector2D& pos, bool avoidMovingUnits) +{ + // If we don't have a short path now + if (m_ShortPath.m_Waypoints.empty()) + { + // Try to pick a new long waypoint (which will also recompute the short path) + if (!PickNextWaypoint(pos, avoidMovingUnits)) + return false; // no waypoints left + + if (m_ShortPath.m_Waypoints.empty()) + return false; // we can't reach the next long waypoint or are already there + } + + // Head towards the next short waypoint + m_ShortTargetX = m_ShortPath.m_Waypoints.back().x; + m_ShortTargetZ = m_ShortPath.m_Waypoints.back().z; + m_ShortPath.m_Waypoints.pop_back(); + m_HasTarget = true; + return true; +} + +void CCmpUnitMotion::RenderPath(const CSimContext& context, const ICmpPathfinder::Path& path, std::vector& lines, CColor color) +{ + lines.clear(); + std::vector waypointCoords; + for (size_t i = 0; i < path.m_Waypoints.size(); ++i) + { + float x = path.m_Waypoints[i].x.ToFloat(); + float z = path.m_Waypoints[i].z.ToFloat(); + waypointCoords.push_back(x); + waypointCoords.push_back(z); + lines.push_back(SOverlayLine()); + lines.back().m_Color = color; + SimRender::ConstructSquareOnGround(context, x, z, 1.0f, 1.0f, 0.0f, lines.back()); + } + lines.push_back(SOverlayLine()); + lines.back().m_Color = color; + SimRender::ConstructLineOnGround(context, waypointCoords, lines.back()); + +} + +void CCmpUnitMotion::RenderSubmit(const CSimContext& UNUSED(context), SceneCollector& collector) +{ + if (!m_DebugOverlayEnabled) + return; + + for (size_t i = 0; i < m_DebugOverlayLines.size(); ++i) + collector.Submit(&m_DebugOverlayLines[i]); + + for (size_t i = 0; i < m_DebugOverlayShortPathLines.size(); ++i) + collector.Submit(&m_DebugOverlayShortPathLines[i]); } Index: ps/trunk/source/simulation2/components/ICmpUnitMotion.cpp =================================================================== --- ps/trunk/source/simulation2/components/ICmpUnitMotion.cpp (revision 7483) +++ ps/trunk/source/simulation2/components/ICmpUnitMotion.cpp (revision 7484) @@ -1,27 +1,30 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #include "precompiled.h" #include "ICmpUnitMotion.h" #include "simulation2/system/InterfaceScripted.h" BEGIN_INTERFACE_WRAPPER(UnitMotion) -DEFINE_INTERFACE_METHOD_4("MoveToPoint", void, ICmpUnitMotion, MoveToPoint, entity_pos_t, entity_pos_t, entity_pos_t, entity_pos_t) +DEFINE_INTERFACE_METHOD_2("MoveToPoint", bool, ICmpUnitMotion, MoveToPoint, entity_pos_t, entity_pos_t) +DEFINE_INTERFACE_METHOD_3("IsInAttackRange", bool, ICmpUnitMotion, IsInAttackRange, entity_id_t, entity_pos_t, entity_pos_t) +DEFINE_INTERFACE_METHOD_3("MoveToAttackRange", bool, ICmpUnitMotion, MoveToAttackRange, entity_id_t, entity_pos_t, entity_pos_t) DEFINE_INTERFACE_METHOD_0("GetSpeed", CFixed_23_8, ICmpUnitMotion, GetSpeed) +DEFINE_INTERFACE_METHOD_1("SetDebugOverlay", void, ICmpUnitMotion, SetDebugOverlay, bool) END_INTERFACE_WRAPPER(UnitMotion) Index: ps/trunk/source/simulation2/components/ICmpObstructionManager.h =================================================================== --- ps/trunk/source/simulation2/components/ICmpObstructionManager.h (revision 7483) +++ ps/trunk/source/simulation2/components/ICmpObstructionManager.h (revision 7484) @@ -1,175 +1,239 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #ifndef INCLUDED_ICMPOBSTRUCTIONMANAGER #define INCLUDED_ICMPOBSTRUCTIONMANAGER #include "simulation2/system/Interface.h" #include "simulation2/helpers/Grid.h" #include "simulation2/helpers/Position.h" +#include "maths/FixedVector2D.h" + class IObstructionTestFilter; /** * Obstruction manager: provides efficient spatial queries over objects in the world. * - * The class exposes the abstraction of "shapes", which represent circles or squares - * with certain properties. + * The class deals with two types of shape: + * "static" shapes, typically representing buildings, which are rectangles with a given + * width and height and angle; + * and "unit" shapes, representing units that can move around the world, which have a + * radius and no rotation. (Units sometimes act as axis-aligned squares, sometimes + * as approximately circles, due to the algorithm used by the short pathfinder.) + * * Other classes (particularly ICmpObstruction) register shapes with this interface * and keep them updated. * * The @c Test functions provide exact collision tests. * The edge of a shape counts as 'inside' the shape, for the purpose of collisions. * The functions accept an IObstructionTestFilter argument, which can restrict the * set of shapes that are counted as collisions. * + * Units can be marked as either moving or stationary, which simply determines whether + * certain filters include or exclude them. + * * The @c Rasterise function approximates the current set of shapes onto a 2D grid, - * primarily for pathfinding. + * for use with tile-based pathfinding. */ class ICmpObstructionManager : public IComponent { public: /** * External identifiers for shapes. Valid tags are guaranteed to be non-zero. */ typedef u32 tag_t; /** - * Register a circle. + * Register a static shape. * @param x X coordinate of center, in world space * @param z Z coordinate of center, in world space - * @param r radius + * @param a angle of rotation (clockwise from +Z direction) + * @param w width (size along X axis) + * @param h height (size along Z axis) * @return a valid tag for manipulating the shape */ - virtual tag_t AddCircle(entity_pos_t x, entity_pos_t z, entity_pos_t r) = 0; + virtual tag_t AddStaticShape(entity_pos_t x, entity_pos_t z, entity_angle_t a, entity_pos_t w, entity_pos_t h) = 0; /** - * Register a square. + * Register a unit shape. * @param x X coordinate of center, in world space * @param z Z coordinate of center, in world space - * @param a angle of rotation (clockwise from +Z direction) - * @param w width (size along X axis) - * @param h height (size along Z axis) + * @param r radius (half the unit's width/height) + * @param moving whether the unit is currently moving through the world or is stationary * @return a valid tag for manipulating the shape */ - virtual tag_t AddSquare(entity_pos_t x, entity_pos_t z, entity_angle_t a, entity_pos_t w, entity_pos_t h) = 0; + virtual tag_t AddUnitShape(entity_pos_t x, entity_pos_t z, entity_angle_t r, bool moving) = 0; /** * Adjust the position and angle of an existing shape. * @param tag tag of shape (must be valid) * @param x X coordinate of center, in world space * @param z Z coordinate of center, in world space - * @param a angle of rotation (clockwise from +Z direction); ignored for circles + * @param a angle of rotation (clockwise from +Z direction); ignored for unit shapes */ virtual void MoveShape(tag_t tag, entity_pos_t x, entity_pos_t z, entity_angle_t a) = 0; /** + * Set whether a unit shape is moving or stationary. + * @param tag tag of shape (must be valid and a unit shape) + * @param moving whether the unit is currently moving through the world or is stationary + */ + virtual void SetUnitMovingFlag(tag_t tag, bool moving) = 0; + + /** * Remove an existing shape. The tag will be made invalid and must not be used after this. * @param tag tag of shape (must be valid) */ virtual void RemoveShape(tag_t tag) = 0; /** * Collision test a flat-ended thick line against the current set of shapes. + * The line caps extend by @p r beyond the end points. + * Only intersections going from outside to inside a shape are counted. * @param filter filter to restrict the shapes that are counted * @param x0 X coordinate of line's first point * @param z0 Z coordinate of line's first point * @param x1 X coordinate of line's second point * @param z1 Z coordinate of line's second point * @param r radius (half width) of line - * @return false if there is a collision + * @return true if there is a collision */ virtual bool TestLine(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r) = 0; /** - * Collision test a circle against the current set of shapes. + * Collision test a static square shape against the current set of shapes. * @param filter filter to restrict the shapes that are counted * @param x X coordinate of center * @param z Z coordinate of center - * @param r radius of circle - * @return false if there is a collision + * @param a angle of rotation (clockwise from +Z direction) + * @param w width (size along X axis) + * @param h height (size along Z axis) + * @return true if there is a collision */ - virtual bool TestCircle(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r) = 0; + virtual bool TestStaticShape(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h) = 0; /** - * Collision test a square against the current set of shapes. + * Collision test a unit shape against the current set of shapes. * @param filter filter to restrict the shapes that are counted * @param x X coordinate of center * @param z Z coordinate of center - * @param a angle of rotation (clockwise from +Z direction) - * @param w width (size along X axis) - * @param h height (size along Z axis) - * @return false if there is a collision + * @param r radius (half the unit's width/height) + * @return true if there is a collision */ - virtual bool TestSquare(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h) = 0; + virtual bool TestUnitShape(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r) = 0; /** * Convert the current set of shapes onto a grid. * Tiles that are partially or completely intersected by a shape will be set to 1; * others will be set to 0. * This is very cheap if the grid has been rasterised before and the set of shapes has not changed. * @param grid the grid to be updated * @return true if any changes were made to the grid, false if it was already up-to-date */ virtual bool Rasterise(Grid& grid) = 0; /** + * Standard representation for all types of shapes, for use with geometry processing code. + */ + struct ObstructionSquare + { + entity_pos_t x, z; // position of center + CFixedVector2D u, v; // 'horizontal' and 'vertical' orthogonal unit vectors, representing orientation + entity_pos_t hw, hh; // half width, half height of square + }; + + /** + * Find all the obstructions that are inside (or partially inside) the given range. + * @param filter filter to restrict the shapes that are counted + * @param x0 X coordinate of left edge of range + * @param z0 Z coordinate of bottom edge of range + * @param x1 X coordinate of right edge of range + * @param z1 Z coordinate of top edge of range + * @param squares output list of obstructions + */ + virtual void GetObstructionsInRange(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, std::vector& squares) = 0; + + /** + * Find a single obstruction that blocks a unit at the given point with the given radius. + * Static obstructions (buildings) are more important than unit obstructions, and + * obstructions that cover the given point are more important than those that only cover + * the point expanded by the radius. + */ + virtual bool FindMostImportantObstruction(entity_pos_t x, entity_pos_t z, entity_pos_t r, ObstructionSquare& square) = 0; + + /** + * Get the obstruction square representing the given shape. + * @param tag tag of shape (must be valid) + */ + virtual ObstructionSquare GetObstruction(tag_t tag) = 0; + + /** * Toggle the rendering of debug info. */ virtual void SetDebugOverlay(bool enabled) = 0; DECLARE_INTERFACE_TYPE(ObstructionManager) }; /** * Interface for ICmpObstructionManager @c Test functions to filter out unwanted shapes. */ class IObstructionTestFilter { public: virtual ~IObstructionTestFilter() {} /** * Return true if the shape should be counted for collisions. * This is called for all shapes that would collide, and also for some that wouldn't. * @param tag tag of shape being tested */ - virtual bool Allowed(ICmpObstructionManager::tag_t tag) const = 0; + virtual bool Allowed(ICmpObstructionManager::tag_t tag, bool moving) const = 0; }; /** * Obstruction test filter that accepts all shapes. */ class NullObstructionFilter : public IObstructionTestFilter { public: - virtual bool Allowed(ICmpObstructionManager::tag_t UNUSED(tag)) const { return true; } + virtual bool Allowed(ICmpObstructionManager::tag_t UNUSED(tag), bool UNUSED(moving)) const { return true; } +}; + +/** + * Obstruction test filter that accepts all non-moving shapes. + */ +class StationaryObstructionFilter : public IObstructionTestFilter +{ +public: + virtual bool Allowed(ICmpObstructionManager::tag_t UNUSED(tag), bool moving) const { return !moving; } }; /** * Obstruction test filter that rejects a specific shape. */ class SkipTagObstructionFilter : public IObstructionTestFilter { ICmpObstructionManager::tag_t m_Tag; public: SkipTagObstructionFilter(ICmpObstructionManager::tag_t tag) : m_Tag(tag) {} - virtual bool Allowed(ICmpObstructionManager::tag_t tag) const { return tag != m_Tag; } + virtual bool Allowed(ICmpObstructionManager::tag_t tag, bool UNUSED(moving)) const { return tag != m_Tag; } }; #endif // INCLUDED_ICMPOBSTRUCTIONMANAGER Index: ps/trunk/source/simulation2/components/CCmpPathfinder.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpPathfinder.cpp (revision 7483) +++ ps/trunk/source/simulation2/components/CCmpPathfinder.cpp (revision 7484) @@ -1,743 +1,1117 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #include "precompiled.h" #include "simulation2/system/Component.h" #include "ICmpPathfinder.h" #include "simulation2/MessageTypes.h" #include "ICmpObstructionManager.h" +#include "graphics/Overlay.h" #include "graphics/Terrain.h" #include "maths/FixedVector2D.h" #include "maths/MathUtil.h" #include "ps/Overlay.h" #include "ps/Profile.h" +#include "renderer/Scene.h" #include "renderer/TerrainOverlay.h" +#include "simulation2/helpers/Render.h" +#include "simulation2/helpers/Geometry.h" + +/* + * Note this file contains two separate pathfinding implementations, the 'normal' tile-based + * one and the precise vertex-based 'short' pathfinder. + * They share a priority queue implementation but have independent A* implementations + * (with slightly different characteristics). + */ #ifdef NDEBUG #define PATHFIND_DEBUG 0 #else #define PATHFIND_DEBUG 1 #endif #define PATHFIND_STATS 0 class CCmpPathfinder; struct PathfindTile; +typedef CFixed_23_8 fixed; + /** * Terrain overlay for pathfinder debugging. * Renders a representation of the most recent pathfinding operation. */ class PathfinderOverlay : public TerrainOverlay { NONCOPYABLE(PathfinderOverlay); public: CCmpPathfinder& m_Pathfinder; PathfinderOverlay(CCmpPathfinder& pathfinder) : m_Pathfinder(pathfinder) { } virtual void EndRender(); virtual void ProcessTile(ssize_t i, ssize_t j); }; /** * Implementation of ICmpPathfinder */ class CCmpPathfinder : public ICmpPathfinder { public: - static void ClassInit(CComponentManager& UNUSED(componentManager)) + static void ClassInit(CComponentManager& componentManager) { + componentManager.SubscribeToMessageType(MT_RenderSubmit); // for debug overlays } DEFAULT_COMPONENT_ALLOCATOR(Pathfinder) const CSimContext* m_Context; u16 m_MapSize; // tiles per side Grid* m_Grid; // terrain/passability information // Debugging - output from last pathfind operation: Grid* m_DebugGrid; u32 m_DebugSteps; Path* m_DebugPath; PathfinderOverlay* m_DebugOverlay; + std::vector m_DebugOverlayShortPathLines; + static std::string GetSchema() { return ""; } virtual void Init(const CSimContext& context, const CParamNode& UNUSED(paramNode)) { m_Context = &context; m_MapSize = 0; m_Grid = NULL; m_DebugOverlay = NULL; m_DebugGrid = NULL; m_DebugPath = NULL; } virtual void Deinit(const CSimContext& UNUSED(context)) { delete m_Grid; delete m_DebugOverlay; delete m_DebugGrid; delete m_DebugPath; } virtual void Serialize(ISerializer& serialize) { // TODO: do something here // (Do we need to serialise the pathfinder state, or is it fine to regenerate it from // the original entities after deserialisation?) } virtual void Deserialize(const CSimContext& context, const CParamNode& paramNode, IDeserializer& deserialize) { Init(context, paramNode); // TODO } - virtual bool CanMoveStraight(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r, u32& cost); + virtual void HandleMessage(const CSimContext& context, const CMessage& msg, bool UNUSED(global)) + { + switch (msg.GetType()) + { + case MT_RenderSubmit: + { + const CMessageRenderSubmit& msgData = static_cast (msg); + RenderSubmit(context, msgData.collector); + break; + } + } + } virtual void ComputePath(entity_pos_t x0, entity_pos_t z0, const Goal& goal, Path& ret); + virtual void ComputeShortPath(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t r, entity_pos_t range, const Goal& goal, Path& ret); + virtual void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const Goal& goal) { if (!m_DebugOverlay) return; delete m_DebugGrid; m_DebugGrid = NULL; delete m_DebugPath; m_DebugPath = new Path(); ComputePath(x0, z0, goal, *m_DebugPath); } virtual void SetDebugOverlay(bool enabled) { if (enabled && !m_DebugOverlay) { m_DebugOverlay = new PathfinderOverlay(*this); } else if (!enabled && m_DebugOverlay) { delete m_DebugOverlay; m_DebugOverlay = NULL; } } /** * Returns the tile containing the given position */ void NearestTile(entity_pos_t x, entity_pos_t z, u16& i, u16& j) { - i = clamp((x / CELL_SIZE).ToInt_RoundToZero(), 0, m_MapSize-1); - j = clamp((z / CELL_SIZE).ToInt_RoundToZero(), 0, m_MapSize-1); + i = clamp((x / (int)CELL_SIZE).ToInt_RoundToZero(), 0, m_MapSize-1); + j = clamp((z / (int)CELL_SIZE).ToInt_RoundToZero(), 0, m_MapSize-1); } /** * Returns the position of the center of the given tile */ - void TileCenter(u16 i, u16 j, entity_pos_t& x, entity_pos_t& z) + static void TileCenter(u16 i, u16 j, entity_pos_t& x, entity_pos_t& z) { - x = entity_pos_t::FromInt(i*CELL_SIZE + CELL_SIZE/2); - z = entity_pos_t::FromInt(j*CELL_SIZE + CELL_SIZE/2); + x = entity_pos_t::FromInt(i*(int)CELL_SIZE + CELL_SIZE/2); + z = entity_pos_t::FromInt(j*(int)CELL_SIZE + CELL_SIZE/2); } /** * Regenerates the grid based on the current obstruction list, if necessary */ void UpdateGrid() { PROFILE("UpdateGrid"); // Initialise the terrain data when first needed if (!m_Grid) { // TOOD: these bits should come from ICmpTerrain ssize_t size = m_Context->GetTerrain().GetTilesPerSide(); debug_assert(size >= 1 && size <= 0xffff); // must fit in 16 bits m_MapSize = size; m_Grid = new Grid(m_MapSize, m_MapSize); } CmpPtr cmpObstructionManager(*m_Context, SYSTEM_ENTITY); cmpObstructionManager->Rasterise(*m_Grid); } + + void RenderSubmit(const CSimContext& context, SceneCollector& collector); }; REGISTER_COMPONENT_TYPE(Pathfinder) const u32 g_CostPerTile = 256; // base cost to move between adjacent tiles -bool CCmpPathfinder::CanMoveStraight(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r, u32& cost) -{ - // Test whether there's a straight path - CmpPtr cmpObstructionManager(*m_Context, SYSTEM_ENTITY); - NullObstructionFilter filter; - if (!cmpObstructionManager->TestLine(filter, x0, z0, x1, z1, r)) - return false; - - // Calculate the exact movement cost - // (TODO: this needs to care about terrain costs etc) - cost = (CFixedVector2D(x1 - x0, z1 - z0).Length() * g_CostPerTile).ToInt_RoundToZero(); - - return true; -} - /** * Tile data for A* computation */ struct PathfindTile { enum { STATUS_UNEXPLORED = 0, STATUS_OPEN = 1, STATUS_CLOSED = 2 }; u8 status; // (TODO: this only needs 2 bits) u16 pi, pj; // predecessor on best path (TODO: this only needs 2 bits) u32 cost; // g (cost to this tile) u32 h; // h (TODO: is it really better for performance to store this instead of recomputing?) u32 step; // step at which this tile was last processed (TODO: this should only be present for debugging) }; void PathfinderOverlay::EndRender() { if (m_Pathfinder.m_DebugPath) { std::vector& wp = m_Pathfinder.m_DebugPath->m_Waypoints; for (size_t n = 0; n < wp.size(); ++n) { u16 i, j; m_Pathfinder.NearestTile(wp[n].x, wp[n].z, i, j); RenderTileOutline(CColor(1, 1, 1, 1), 2, false, i, j); } } } void PathfinderOverlay::ProcessTile(ssize_t i, ssize_t j) { if (m_Pathfinder.m_Grid && m_Pathfinder.m_Grid->get(i, j)) RenderTile(CColor(1, 0, 0, 0.6f), false); if (m_Pathfinder.m_DebugGrid) { PathfindTile& n = m_Pathfinder.m_DebugGrid->get(i, j); float c = clamp(n.step / (float)m_Pathfinder.m_DebugSteps, 0.f, 1.f); if (n.status == PathfindTile::STATUS_OPEN) RenderTile(CColor(1, 1, c, 0.6f), false); else if (n.status == PathfindTile::STATUS_CLOSED) RenderTile(CColor(0, 1, c, 0.6f), false); } } /* * A* pathfinding implementation * * This is currently all a bit rubbish and hasn't been tested for correctness or efficiency; * the intention is to demonstrate the interface that the pathfinder can use, and improvements * to the implementation shouldn't affect that interface much. */ -struct QueueItem -{ - u16 i, j; - u32 rank; // g+h (estimated total cost of path through here) -}; - +template struct QueueItemPriority { - bool operator()(const QueueItem& a, const QueueItem& b) + bool operator()(const Item& a, const Item& b) { if (a.rank > b.rank) // higher costs are lower priority return true; if (a.rank < b.rank) return false; // Need to tie-break to get a consistent ordering // TODO: Should probably tie-break on g or h or something, but don't bother for now - if (a.i < b.i) - return true; - if (a.i > b.i) - return false; - if (a.j < b.j) + if (a.id < b.id) return true; - if (a.j > b.j) + if (b.id < a.id) return false; #if PATHFIND_DEBUG debug_warn(L"duplicate tiles in queue"); #endif return false; } }; /** * Priority queue implemented as a binary heap. * This is quite dreadfully slow in MSVC's debug STL implementation, * so we shouldn't use it unless we reimplement the heap functions more efficiently. */ +template class PriorityQueueHeap { public: - void push(const QueueItem& item) + struct Item + { + ID id; + R rank; // f = g+h (estimated total cost of path through here) + }; + + void push(const Item& item) { m_Heap.push_back(item); - push_heap(m_Heap.begin(), m_Heap.end(), QueueItemPriority()); + push_heap(m_Heap.begin(), m_Heap.end(), QueueItemPriority()); } - QueueItem* find(u16 i, u16 j) + Item* find(ID id) { for (size_t n = 0; n < m_Heap.size(); ++n) { - if (m_Heap[n].i == i && m_Heap[n].j == j) + if (m_Heap[n].id == id) return &m_Heap[n]; } return NULL; } - void promote(u16 i, u16 j, u32 newrank) + void promote(ID id, u32 newrank) { for (size_t n = 0; n < m_Heap.size(); ++n) { - if (m_Heap[n].i == i && m_Heap[n].j == j) + if (m_Heap[n].id == id) { #if PATHFIND_DEBUG debug_assert(m_Heap[n].rank > newrank); #endif m_Heap[n].rank = newrank; - push_heap(m_Heap.begin(), m_Heap.begin()+n+1, QueueItemPriority()); + push_heap(m_Heap.begin(), m_Heap.begin()+n+1, QueueItemPriority()); return; } } } - QueueItem pop() + Item pop() { #if PATHFIND_DEBUG debug_assert(m_Heap.size()); #endif - QueueItem r = m_Heap.front(); - pop_heap(m_Heap.begin(), m_Heap.end(), QueueItemPriority()); + Item r = m_Heap.front(); + pop_heap(m_Heap.begin(), m_Heap.end(), QueueItemPriority()); m_Heap.pop_back(); return r; } bool empty() { return m_Heap.empty(); } size_t size() { return m_Heap.size(); } - std::vector m_Heap; + std::vector m_Heap; }; /** * Priority queue implemented as an unsorted array. * This means pop() is O(n), but push and promote are O(1), and n is typically small * (average around 50-100 in some rough tests). * It seems fractionally slower than a binary heap in optimised builds, but is * much simpler and less susceptible to MSVC's painfully slow debug STL. */ +template class PriorityQueueList { public: - void push(const QueueItem& item) + struct Item + { + ID id; + R rank; // f = g+h (estimated total cost of path through here) + }; + + void push(const Item& item) { m_List.push_back(item); } - QueueItem* find(u16 i, u16 j) + Item* find(ID id) { for (size_t n = 0; n < m_List.size(); ++n) { - if (m_List[n].i == i && m_List[n].j == j) + if (m_List[n].id == id) return &m_List[n]; } return NULL; } - void promote(u16 i, u16 j, u32 newrank) + void promote(ID id, R newrank) { - find(i, j)->rank = newrank; + find(id)->rank = newrank; } - QueueItem pop() + Item pop() { #if PATHFIND_DEBUG debug_assert(m_List.size()); #endif // Loop backwards looking for the best (it's most likely to be one // we've recently pushed, so going backwards saves a bit of copying) - QueueItem best = m_List.back(); + Item best = m_List.back(); size_t bestidx = m_List.size()-1; for (ssize_t i = (ssize_t)bestidx-1; i >= 0; --i) { - if (QueueItemPriority()(best, m_List[i])) + if (QueueItemPriority()(best, m_List[i])) { bestidx = i; best = m_List[i]; } } // Swap the matched element with the last in the list, then pop the new last m_List[bestidx] = m_List[m_List.size()-1]; m_List.pop_back(); return best; } bool empty() { return m_List.empty(); } size_t size() { return m_List.size(); } - std::vector m_List; + std::vector m_List; }; -typedef PriorityQueueList PriorityQueue; +typedef PriorityQueueList, u32> PriorityQueue; #define USE_DIAGONAL_MOVEMENT // Calculate heuristic cost from tile i,j to destination // (This ought to be an underestimate for correctness) -static u32 CalculateHeuristic(u16 i, u16 j, u16 iGoal, u16 jGoal, u16 rGoal, bool aimingInwards) +static u32 CalculateHeuristic(u16 i, u16 j, u16 iGoal, u16 jGoal, u16 rGoal) { #ifdef USE_DIAGONAL_MOVEMENT CFixedVector2D pos (CFixed_23_8::FromInt(i), CFixed_23_8::FromInt(j)); CFixedVector2D goal (CFixed_23_8::FromInt(iGoal), CFixed_23_8::FromInt(jGoal)); CFixed_23_8 dist = (pos - goal).Length(); // TODO: the heuristic could match the costs better - it's not really Euclidean movement CFixed_23_8 rdist = dist - CFixed_23_8::FromInt(rGoal); - if (!aimingInwards) - rdist = -rdist; + rdist = rdist.Absolute(); - if (rdist < CFixed_23_8::FromInt(0)) - return 0; - return (rdist * g_CostPerTile).ToInt_RoundToZero(); + return (rdist * (int)g_CostPerTile).ToInt_RoundToZero(); #else return (abs((int)i - (int)iGoal) + abs((int)j - (int)jGoal)) * g_CostPerTile; #endif } // Calculate movement cost from predecessor tile pi,pj to tile i,j static u32 CalculateCostDelta(u16 pi, u16 pj, u16 i, u16 j, Grid* tempGrid) { u32 dg = g_CostPerTile; #ifdef USE_DIAGONAL_MOVEMENT // XXX: Probably a terrible hack: // For simplicity, we only consider horizontally/vertically adjacent neighbours, but // units can move along arbitrary lines. That results in ugly square paths, so we want // to prefer diagonal paths. // Instead of solving this nicely, I'll just special-case 45-degree and 30-degree lines // by checking the three predecessor tiles (which'll be in the closed set and therefore // likely to be reasonably stable) and reducing the cost, and use a Euclidean heuristic. // At least this makes paths look a bit nicer for now... PathfindTile& p = tempGrid->get(pi, pj); if (p.pi != i && p.pj != j) dg = (dg << 16) / 92682; // dg*sqrt(2)/2 else { PathfindTile& pp = tempGrid->get(p.pi, p.pj); int di = abs(i - pp.pi); int dj = abs(j - pp.pj); if ((di == 1 && dj == 2) || (di == 2 && dj == 1)) dg = (dg << 16) / 79742; // dg*(sqrt(5)-sqrt(2)) } #endif return dg; } struct PathfinderState { u32 steps; // number of algorithm iterations u16 iGoal, jGoal; // goal tile u16 rGoal; // radius of goal (around tile center) - bool aimingInwards; // whether we're moving towards the goal or away PriorityQueue open; // (there's no explicit closed list; it's encoded in PathfindTile::status) Grid* tiles; Grid* terrain; u32 hBest; // heuristic of closest discovered tile to goal u16 iBest, jBest; // closest tile #if PATHFIND_STATS // Performance debug counters size_t numProcessed; size_t numImproveOpen; size_t numImproveClosed; size_t numAddToOpen; size_t sumOpenSize; #endif }; // Do the A* processing for a neighbour tile i,j. static void ProcessNeighbour(u16 pi, u16 pj, u16 i, u16 j, u32 pg, PathfinderState& state) { #if PATHFIND_STATS state.numProcessed++; #endif // Reject impassable tiles if (state.terrain->get(i, j)) return; u32 dg = CalculateCostDelta(pi, pj, i, j, state.tiles); u32 g = pg + dg; // cost to this tile = cost to predecessor + delta from predecessor PathfindTile& n = state.tiles->get(i, j); // If this is a new tile, compute the heuristic distance if (n.status == PathfindTile::STATUS_UNEXPLORED) { - n.h = CalculateHeuristic(i, j, state.iGoal, state.jGoal, state.rGoal, state.aimingInwards); + n.h = CalculateHeuristic(i, j, state.iGoal, state.jGoal, state.rGoal); // Remember the best tile we've seen so far, in case we never actually reach the target if (n.h < state.hBest) { state.hBest = n.h; state.iBest = i; state.jBest = j; } } else { // If we've already seen this tile, and the new path to this tile does not have a // better cost, then stop now if (g >= n.cost) return; // Otherwise, we have a better path. // If we've already added this tile to the open list: if (n.status == PathfindTile::STATUS_OPEN) { // This is a better path, so replace the old one with the new cost/parent n.cost = g; n.pi = pi; n.pj = pj; n.step = state.steps; - state.open.promote(i, j, g + n.h); + state.open.promote(std::make_pair(i, j), g + n.h); #if PATHFIND_STATS state.numImproveOpen++; #endif return; } // If we've already found the 'best' path to this tile: if (n.status == PathfindTile::STATUS_CLOSED) { // This is a better path (possible when we use inadmissible heuristics), so reopen it #if PATHFIND_STATS state.numImproveClosed++; #endif // (fall through) } } // Add it to the open list: n.status = PathfindTile::STATUS_OPEN; n.cost = g; n.pi = pi; n.pj = pj; n.step = state.steps; - QueueItem t = { i, j, g + n.h }; + PriorityQueue::Item t = { std::make_pair(i, j), g + n.h }; state.open.push(t); #if PATHFIND_STATS state.numAddToOpen++; #endif } -static bool AtGoal(u16 i, u16 j, u16 iGoal, u16 jGoal, u16 rGoal, bool aimingInwards) +static fixed DistanceToGoal(CFixedVector2D pos, const CCmpPathfinder::Goal& goal) { - // If we're aiming towards a point, stop when we get there - if (aimingInwards && rGoal == 0) - return (i == iGoal && j == jGoal); - - // Otherwise compute the distance and compare to desired radius - i32 dist2 = ((i32)i-iGoal)*((i32)i-iGoal) + ((i32)j-jGoal)*((i32)j-jGoal); - if (aimingInwards && (dist2 <= rGoal*rGoal)) - return true; - if (!aimingInwards && (dist2 >= rGoal*rGoal)) - return true; + switch (goal.type) + { + case CCmpPathfinder::Goal::POINT: + return (pos - CFixedVector2D(goal.x, goal.z)).Length(); + + case CCmpPathfinder::Goal::CIRCLE: + return ((pos - CFixedVector2D(goal.x, goal.z)).Length() - goal.hw).Absolute(); + + case CCmpPathfinder::Goal::SQUARE: + { + CFixedVector2D halfSize(goal.hw, goal.hh); + CFixedVector2D d(pos.X - goal.x, pos.Y - goal.z); + return Geometry::DistanceToSquare(d, goal.u, goal.v, halfSize); + } - return false; + default: + debug_warn(L"invalid type"); + return fixed::Zero(); + } +} + +static bool AtGoal(u16 i, u16 j, const ICmpPathfinder::Goal& goal) +{ + // Allow tiles slightly more than sqrt(2) from the actual goal, + // i.e. adjacent diagonally to the target tile + fixed tolerance = entity_pos_t::FromInt(CELL_SIZE*3/2); + + entity_pos_t x, z; + CCmpPathfinder::TileCenter(i, j, x, z); + fixed dist = DistanceToGoal(CFixedVector2D(x, z), goal); + return (dist < tolerance); } void CCmpPathfinder::ComputePath(entity_pos_t x0, entity_pos_t z0, const Goal& goal, Path& path) { UpdateGrid(); PROFILE("ComputePath"); PathfinderState state = { 0 }; // Convert the start/end coordinates to tile indexes u16 i0, j0; NearestTile(x0, z0, i0, j0); NearestTile(goal.x, goal.z, state.iGoal, state.jGoal); - // If we start closer than min radius, aim for the min radius - // If we start further than max radius, aim for the max radius - // Otherwise we're there already - CFixed_23_8 initialDist = (CFixedVector2D(x0, z0) - CFixedVector2D(goal.x, goal.z)).Length(); - if (initialDist < goal.minRadius) - { - state.aimingInwards = false; - state.rGoal = (goal.minRadius / CELL_SIZE).ToInt_RoundToZero(); // TODO: what rounding mode is appropriate? - } - else if (initialDist > goal.maxRadius) - { - state.aimingInwards = true; - state.rGoal = (goal.maxRadius / CELL_SIZE).ToInt_RoundToZero(); // TODO: what rounding mode is appropriate? - } - else - { - return; - } - // If we're already at the goal tile, then move directly to the exact goal coordinates - if (AtGoal(i0, j0, state.iGoal, state.jGoal, state.rGoal, state.aimingInwards)) + if (AtGoal(i0, j0, goal)) { - Waypoint w = { goal.x, goal.z, 0 }; + Waypoint w = { goal.x, goal.z }; path.m_Waypoints.push_back(w); return; } + // If the target is a circle, we want to aim for the edge of it (so e.g. if we're inside + // a large circle then the heuristics will aim us directly outwards); + // otherwise just aim at the center point. (We'll never try moving outwards to a square shape.) + if (goal.type == Goal::CIRCLE) + state.rGoal = (goal.hw / (int)CELL_SIZE).ToInt_RoundToZero(); + else + state.rGoal = 0; + state.steps = 0; state.tiles = new Grid(m_MapSize, m_MapSize); state.terrain = m_Grid; state.iBest = i0; state.jBest = j0; - state.hBest = CalculateHeuristic(i0, j0, state.iGoal, state.jGoal, state.rGoal, state.aimingInwards); + state.hBest = CalculateHeuristic(i0, j0, state.iGoal, state.jGoal, state.rGoal); - QueueItem start = { i0, j0, 0 }; + PriorityQueue::Item start = { std::make_pair(i0, j0), 0 }; state.open.push(start); state.tiles->get(i0, j0).status = PathfindTile::STATUS_OPEN; state.tiles->get(i0, j0).pi = i0; state.tiles->get(i0, j0).pj = j0; state.tiles->get(i0, j0).cost = 0; while (1) { ++state.steps; // Hack to avoid spending ages computing giant paths, particularly when // the destination is unreachable if (state.steps > 5000) break; // If we ran out of tiles to examine, give up if (state.open.empty()) break; #if PATHFIND_STATS state.sumOpenSize += state.open.size(); #endif // Move best tile from open to closed - QueueItem curr = state.open.pop(); - state.tiles->get(curr.i, curr.j).status = PathfindTile::STATUS_CLOSED; + PriorityQueue::Item curr = state.open.pop(); + u16 i = curr.id.first; + u16 j = curr.id.second; + state.tiles->get(i, j).status = PathfindTile::STATUS_CLOSED; // If we've reached the destination, stop - if (AtGoal(curr.i, curr.j, state.iGoal, state.jGoal, state.rGoal, state.aimingInwards)) + if (AtGoal(i, j, goal)) { - state.iBest = curr.i; - state.jBest = curr.j; + state.iBest = i; + state.jBest = j; state.hBest = 0; break; } - u32 g = state.tiles->get(curr.i, curr.j).cost; - if (curr.i > 0) - ProcessNeighbour(curr.i, curr.j, curr.i-1, curr.j, g, state); - if (curr.i < m_MapSize-1) - ProcessNeighbour(curr.i, curr.j, curr.i+1, curr.j, g, state); - if (curr.j > 0) - ProcessNeighbour(curr.i, curr.j, curr.i, curr.j-1, g, state); - if (curr.j < m_MapSize-1) - ProcessNeighbour(curr.i, curr.j, curr.i, curr.j+1, g, state); + u32 g = state.tiles->get(i, j).cost; + if (i > 0) + ProcessNeighbour(i, j, i-1, j, g, state); + if (i < m_MapSize-1) + ProcessNeighbour(i, j, i+1, j, g, state); + if (j > 0) + ProcessNeighbour(i, j, i, j-1, g, state); + if (j < m_MapSize-1) + ProcessNeighbour(i, j, i, j+1, g, state); } // Reconstruct the path (in reverse) u16 ip = state.iBest, jp = state.jBest; while (ip != i0 || jp != j0) { PathfindTile& n = state.tiles->get(ip, jp); - // Pick the exact point if it's the goal tile, else the tile's centre entity_pos_t x, z; - if (ip == state.iGoal && jp == state.jGoal) - { - x = goal.x; - z = goal.z; - } - else - { - TileCenter(ip, jp, x, z); - } - Waypoint w = { x, z, n.cost }; + TileCenter(ip, jp, x, z); + Waypoint w = { x, z }; path.m_Waypoints.push_back(w); // Follow the predecessor link ip = n.pi; jp = n.pj; } // Save this grid for debug display delete m_DebugGrid; m_DebugGrid = state.tiles; m_DebugSteps = state.steps; #if PATHFIND_STATS printf("PATHFINDER: steps=%d avgo=%d proc=%d impc=%d impo=%d addo=%d\n", state.steps, state.sumOpenSize/state.steps, state.numProcessed, state.numImproveClosed, state.numImproveOpen, state.numAddToOpen); #endif } + + +////////////////////////////////////////////////////////// + +struct Vertex +{ + CFixedVector2D p; + fixed g, h; + u16 pred; + enum + { + UNEXPLORED, + OPEN, + CLOSED, + } status; +}; + +struct Edge +{ + CFixedVector2D p0, p1; +}; + +/** + * Check whether a ray from 'a' to 'b' crosses any of the edges. + * (Edges are one-sided so it's only considered a cross if going from front to back.) + */ +static bool CheckVisibility(CFixedVector2D a, CFixedVector2D b, const std::vector& edges) +{ + CFixedVector2D abn = (b - a).Perpendicular(); + + for (size_t i = 0; i < edges.size(); ++i) + { + CFixedVector2D d = (edges[i].p1 - edges[i].p0).Perpendicular(); + + // If 'a' is behind the edge, we can't cross + fixed q = (a - edges[i].p0).Dot(d); + if (q < fixed::Zero()) + continue; + + // If 'b' is in front of the edge, we can't cross + fixed r = (b - edges[i].p0).Dot(d); + if (r > fixed::Zero()) + continue; + + // The ray is crossing the infinitely-extended edge from in front to behind. + // If the edge's points are the same side of the infinitely-extended ray + // then the finite lines can't intersect, otherwise they're crossing + fixed s = (edges[i].p0 - a).Dot(abn); + fixed t = (edges[i].p1 - a).Dot(abn); + if ((s <= fixed::Zero() && t >= fixed::Zero()) || (s >= fixed::Zero() && t <= fixed::Zero())) + return false; + } + + return true; +} + +static CFixedVector2D NearestPointOnGoal(CFixedVector2D pos, const CCmpPathfinder::Goal& goal) +{ + CFixedVector2D g(goal.x, goal.z); + + switch (goal.type) + { + case CCmpPathfinder::Goal::POINT: + { + return g; + } + + case CCmpPathfinder::Goal::CIRCLE: + { + CFixedVector2D d = pos - g; + if (d.IsZero()) + d = CFixedVector2D(fixed::FromInt(1), fixed::Zero()); // some arbitrary direction + d.Normalize(goal.hw); + return g + d; + } + + case CCmpPathfinder::Goal::SQUARE: + { + CFixedVector2D halfSize(goal.hw, goal.hh); + CFixedVector2D d = pos - g; + return g + Geometry::NearestPointOnSquare(d, goal.u, goal.v, halfSize); + } + + default: + debug_warn(L"invalid type"); + return CFixedVector2D(); + } +} + +typedef PriorityQueueList ShortPathPriorityQueue; + +void CCmpPathfinder::ComputeShortPath(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t r, entity_pos_t range, const Goal& goal, Path& path) +{ + PROFILE("ComputeShortPath"); + + m_DebugOverlayShortPathLines.clear(); + + if (m_DebugOverlay) + { + // Render the goal shape + m_DebugOverlayShortPathLines.push_back(SOverlayLine()); + m_DebugOverlayShortPathLines.back().m_Color = CColor(1, 0, 0, 1); + switch (goal.type) + { + case CCmpPathfinder::Goal::POINT: + { + SimRender::ConstructCircleOnGround(*m_Context, goal.x.ToFloat(), goal.z.ToFloat(), 0.2f, m_DebugOverlayShortPathLines.back()); + break; + } + case CCmpPathfinder::Goal::CIRCLE: + { + SimRender::ConstructCircleOnGround(*m_Context, goal.x.ToFloat(), goal.z.ToFloat(), goal.hw.ToFloat(), m_DebugOverlayShortPathLines.back()); + break; + } + case CCmpPathfinder::Goal::SQUARE: + { + float a = atan2(goal.v.X.ToFloat(), goal.v.Y.ToFloat()); + SimRender::ConstructSquareOnGround(*m_Context, goal.x.ToFloat(), goal.z.ToFloat(), goal.hw.ToFloat()*2, goal.hh.ToFloat()*2, a, m_DebugOverlayShortPathLines.back()); + break; + } + } + } + + // List of collision edges - paths must never cross these. + // (Edges are one-sided so intersections are fine in one direction, but not the other direction.) + std::vector edges; + + // Create impassable edges at the max-range boundary, so we can't escape the region + // where we're meant to be searching + fixed rangeXMin = x0 - range; + fixed rangeXMax = x0 + range; + fixed rangeZMin = z0 - range; + fixed rangeZMax = z0 + range; + { + // (The edges are the opposite direction to usual, so it's an inside-out square) + Edge e0 = { CFixedVector2D(rangeXMin, rangeZMin), CFixedVector2D(rangeXMin, rangeZMax) }; + Edge e1 = { CFixedVector2D(rangeXMin, rangeZMax), CFixedVector2D(rangeXMax, rangeZMax) }; + Edge e2 = { CFixedVector2D(rangeXMax, rangeZMax), CFixedVector2D(rangeXMax, rangeZMin) }; + Edge e3 = { CFixedVector2D(rangeXMax, rangeZMin), CFixedVector2D(rangeXMin, rangeZMin) }; + edges.push_back(e0); + edges.push_back(e1); + edges.push_back(e2); + edges.push_back(e3); + } + + + CFixedVector2D goalVec(goal.x, goal.z); + + // List of obstruction vertexes (plus start/end points); we'll try to find paths through + // the graph defined by these vertexes + std::vector vertexes; + + // Add the start point to the graph + Vertex start = { CFixedVector2D(x0, z0), fixed::Zero(), (CFixedVector2D(x0, z0) - goalVec).Length(), 0, Vertex::OPEN }; + vertexes.push_back(start); + const size_t START_VERTEX_ID = 0; + + // Add the goal vertex to the graph. + // Since the goal isn't always a point, this a special magic virtual vertex which moves around - whenever + // we look at it from another vertex, it is moved to be the closest point on the goal shape to that vertex. + Vertex end = { CFixedVector2D(goal.x, goal.z), fixed::Zero(), fixed::Zero(), 0, Vertex::UNEXPLORED }; + vertexes.push_back(end); + const size_t GOAL_VERTEX_ID = 1; + + + // Find all the obstruction squares that might affect us + CmpPtr cmpObstructionManager(*m_Context, SYSTEM_ENTITY); + std::vector squares; + cmpObstructionManager->GetObstructionsInRange(filter, rangeXMin - r, rangeZMin - r, rangeXMax + r, rangeZMax + r, squares); + + // Resize arrays to reduce reallocations + vertexes.reserve(vertexes.size() + squares.size()*4); + edges.reserve(edges.size() + squares.size()*4); + + // Convert each obstruction square into collision edges and search graph vertexes + for (size_t i = 0; i < squares.size(); ++i) + { + CFixedVector2D center(squares[i].x, squares[i].z); + CFixedVector2D u = squares[i].u; + CFixedVector2D v = squares[i].v; + + // Expand the vertexes by the moving unit's collision radius, to find the + // closest we can get to it + + entity_pos_t delta = entity_pos_t::FromInt(1)/4; + // add a small delta so that the vertexes of an edge don't get interpreted + // as crossing the edge (given minor numerical inaccuracies) + CFixedVector2D hd0(squares[i].hw + r + delta, squares[i].hh + r + delta); + CFixedVector2D hd1(squares[i].hw + r + delta, -(squares[i].hh + r + delta)); + + Vertex vert; + vert.status = Vertex::UNEXPLORED; + vert.p.X = center.X - hd0.Dot(u); vert.p.Y = center.Y + hd0.Dot(v); vertexes.push_back(vert); + vert.p.X = center.X - hd1.Dot(u); vert.p.Y = center.Y + hd1.Dot(v); vertexes.push_back(vert); + vert.p.X = center.X + hd0.Dot(u); vert.p.Y = center.Y - hd0.Dot(v); vertexes.push_back(vert); + vert.p.X = center.X + hd1.Dot(u); vert.p.Y = center.Y - hd1.Dot(v); vertexes.push_back(vert); + + // Add the four edges + + CFixedVector2D h0(squares[i].hw + r, squares[i].hh + r); + CFixedVector2D h1(squares[i].hw + r, -(squares[i].hh + r)); + + CFixedVector2D ev0(center.X - h0.Dot(u), center.Y + h0.Dot(v)); + CFixedVector2D ev1(center.X - h1.Dot(u), center.Y + h1.Dot(v)); + CFixedVector2D ev2(center.X + h0.Dot(u), center.Y - h0.Dot(v)); + CFixedVector2D ev3(center.X + h1.Dot(u), center.Y - h1.Dot(v)); + Edge e0 = { ev0, ev1 }; + Edge e1 = { ev1, ev2 }; + Edge e2 = { ev2, ev3 }; + Edge e3 = { ev3, ev0 }; + edges.push_back(e0); + edges.push_back(e1); + edges.push_back(e2); + edges.push_back(e3); + + // TODO: should clip out vertexes and edges that are outside the range, + // to reduce the search space + } + + debug_assert(vertexes.size() < 65536); // we store array indexes as u16 + + if (m_DebugOverlay) + { + // Render the obstruction edges + for (size_t i = 0; i < edges.size(); ++i) + { + m_DebugOverlayShortPathLines.push_back(SOverlayLine()); + m_DebugOverlayShortPathLines.back().m_Color = CColor(0, 1, 1, 1); + std::vector xz; + xz.push_back(edges[i].p0.X.ToFloat()); + xz.push_back(edges[i].p0.Y.ToFloat()); + xz.push_back(edges[i].p1.X.ToFloat()); + xz.push_back(edges[i].p1.Y.ToFloat()); + SimRender::ConstructLineOnGround(*m_Context, xz, m_DebugOverlayShortPathLines.back()); + } + } + + // Do an A* search over the vertex/visibility graph: + + // Since we are just measuring Euclidean distance the heuristic is admissible, + // so we never have to re-examine a node once it's been moved to the closed set. + + // To save time in common cases, we don't precompute a graph of valid edges between vertexes; + // we do it lazily instead. When the search algorithm reaches a vertex, we examine every other + // vertex and see if we can reach it without hitting any collision edges, and ignore the ones + // we can't reach. Since the algorithm can only reach a vertex once (and then it'll be marked + // as closed), we won't be doing any redundant visibility computations. + + PROFILE_START("A*"); + + ShortPathPriorityQueue open; + ShortPathPriorityQueue::Item qiStart = { START_VERTEX_ID, start.h }; + open.push(qiStart); + + u16 idBest = START_VERTEX_ID; + fixed hBest = start.h; + + while (!open.empty()) + { + // Move best tile from open to closed + ShortPathPriorityQueue::Item curr = open.pop(); + vertexes[curr.id].status = Vertex::CLOSED; + + // If we've reached the destination, stop + if (curr.id == GOAL_VERTEX_ID) + { + idBest = curr.id; + break; + } + + for (size_t n = 0; n < vertexes.size(); ++n) + { + if (vertexes[n].status == Vertex::CLOSED) + continue; + + // If this is the magical goal vertex, move it to near the current vertex + CFixedVector2D npos; + if (n == GOAL_VERTEX_ID) + npos = NearestPointOnGoal(vertexes[curr.id].p, goal); + else + npos = vertexes[n].p; + + bool visible = CheckVisibility(vertexes[curr.id].p, npos, edges); + + /* + // Render the edges that we examine + m_DebugOverlayShortPathLines.push_back(SOverlayLine()); + m_DebugOverlayShortPathLines.back().m_Color = visible ? CColor(0, 1, 0, 1) : CColor(0, 0, 0, 1); + std::vector xz; + xz.push_back(vertexes[curr.id].p.X.ToFloat()); + xz.push_back(vertexes[curr.id].p.Y.ToFloat()); + xz.push_back(npos.X.ToFloat()); + xz.push_back(npos.Y.ToFloat()); + SimRender::ConstructLineOnGround(*m_Context, xz, m_DebugOverlayShortPathLines.back()); + //*/ + + if (visible) + { + fixed g = vertexes[curr.id].g + (vertexes[curr.id].p - npos).Length(); + + // If this is a new tile, compute the heuristic distance + if (vertexes[n].status == Vertex::UNEXPLORED) + { + // Add it to the open list: + vertexes[n].status = Vertex::OPEN; + vertexes[n].g = g; + vertexes[n].h = DistanceToGoal(npos, goal); + vertexes[n].pred = curr.id; + if (n == GOAL_VERTEX_ID) + vertexes[n].p = npos; // remember the new best goal position + ShortPathPriorityQueue::Item t = { n, g + vertexes[n].h }; + open.push(t); + + // Remember the heuristically best vertex we've seen so far, in case we never actually reach the target + if (vertexes[n].h < hBest) + { + idBest = n; + hBest = vertexes[n].h; + } + } + else // must be OPEN + { + // If we've already seen this tile, and the new path to this tile does not have a + // better cost, then stop now + if (g >= vertexes[n].g) + continue; + + // Otherwise, we have a better path, so replace the old one with the new cost/parent + vertexes[n].g = g; + vertexes[n].pred = curr.id; + if (n == GOAL_VERTEX_ID) + vertexes[n].p = npos; // remember the new best goal position + open.promote((u16)n, g + vertexes[n].h); + continue; + } + } + } + } + + // Reconstruct the path (in reverse) + for (u16 id = idBest; id != START_VERTEX_ID; id = vertexes[id].pred) + { + Waypoint w = { vertexes[id].p.X, vertexes[id].p.Y }; + path.m_Waypoints.push_back(w); + } + + PROFILE_END("A*"); +} + +////////////////////////////////////////////////////////// + +void CCmpPathfinder::RenderSubmit(const CSimContext& context, SceneCollector& collector) +{ + for (size_t i = 0; i < m_DebugOverlayShortPathLines.size(); ++i) + collector.Submit(&m_DebugOverlayShortPathLines[i]); +} Index: ps/trunk/source/renderer/TerrainOverlay.cpp =================================================================== --- ps/trunk/source/renderer/TerrainOverlay.cpp (revision 7483) +++ ps/trunk/source/renderer/TerrainOverlay.cpp (revision 7484) @@ -1,326 +1,234 @@ /* Copyright (C) 2009 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #include "precompiled.h" #include "TerrainOverlay.h" #include "ps/Overlay.h" #include "ps/Game.h" #include "ps/World.h" #include "graphics/Terrain.h" #include "maths/MathUtil.h" #include "lib/ogl.h" #include // Handy things for STL: /// Functor for sorting pairs, using the <-ordering of their second values. struct compare2nd { template bool operator()(const std::pair& a, const std::pair& b) const { return a.second < b.second; } }; /// Functor for comparing the firsts of pairs to a specified value. template struct equal1st { const S& val; equal1st(const S& val) : val(val) {} template bool operator()(const std::pair& a) const { return a.first == val; } private: const equal1st& operator=(const equal1st& rhs); }; /// Functor for calling ->Render on pairs' firsts. struct render1st { template void operator()(const std::pair& a) const { a.first->Render(); } }; ////////////////////////////////////////////////////////////////////////// // Global overlay list management: static std::vector > g_TerrainOverlayList; TerrainOverlay::TerrainOverlay(int priority) { // Add to global list of overlays g_TerrainOverlayList.push_back(std::make_pair(this, priority)); // Sort by overlays by priority. Do stable sort so that adding/removing // overlays doesn't randomly disturb all the existing ones (which would // be noticeable if they have the same priority and overlap). std::stable_sort(g_TerrainOverlayList.begin(), g_TerrainOverlayList.end(), compare2nd()); } TerrainOverlay::~TerrainOverlay() { std::vector >::iterator newEnd = std::remove_if(g_TerrainOverlayList.begin(), g_TerrainOverlayList.end(), equal1st(this)); g_TerrainOverlayList.erase(newEnd, g_TerrainOverlayList.end()); } - -#if 0 -//initial test to draw out entity boundaries -//it shows how to retrieve object boundary postions for triangulation -//NOTE: it's a test to see how to retrieve bounadry locations for static objects on the terrain. -//disabled -void TerrainOverlay::RenderEntityEdges() -{ - //Kai: added for line drawing - //use a function to encapsulate all the entity boundaries - std::vector results; - - - - g_EntityManager.GetExtant(results); - - glColor3f( 1, 1, 1 ); // Colour outline with player colour - - - - for(size_t i =0 ; i < results.size(); i++) - { - glBegin(GL_LINE_LOOP); - - CEntity* tempHandle = results[i]; - debug_printf(L"Entity position: %f %f %f\n", tempHandle->m_position.X,tempHandle->m_position.Y,tempHandle->m_position.Z); - - CVector2D p, q; - CVector2D u, v; - q.x = tempHandle->m_position.X; - q.y = tempHandle->m_position.Z; - float d = ((CBoundingBox*)tempHandle->m_bounds)->m_d; - float w = ((CBoundingBox*)tempHandle->m_bounds)->m_w; - - u.x = sin( tempHandle->m_graphics_orientation.Y ); - u.y = cos( tempHandle->m_graphics_orientation.Y ); - v.x = u.y; - v.y = -u.x; - - CBoundingObject* m_bounds = tempHandle->m_bounds; - - switch( m_bounds->m_type ) - { - case CBoundingObject::BOUND_CIRCLE: - { - break; - } - case CBoundingObject::BOUND_OABB: - { - //glVertex3f( tempHandle->m_position.X, tempHandle->GetAnchorLevel( tempHandle->m_position.X, tempHandle->m_position.Z ) + 10.0f, tempHandle->m_position.Z ); // lower left vertex - - //glVertex3f( 5, tempHandle->GetAnchorLevel( 5, 5 ) + 0.25f, 5 ); // upper vertex - - p = q + u * d + v * w; - glVertex3f( p.x, tempHandle->GetAnchorLevel( p.x, p.y ) + + 10.0f, p.y ); - - p = q - u * d + v * w ; - glVertex3f( p.x, tempHandle->GetAnchorLevel( p.x, p.y ) + + 10.0f, p.y ); - - p = q - u * d - v * w; - glVertex3f( p.x, tempHandle->GetAnchorLevel( p.x, p.y ) + + 10.0f, p.y ); - - p = q + u * d - v * w; - glVertex3f( p.x, tempHandle->GetAnchorLevel( p.x, p.y ) + + 10.0f, p.y ); - - - break; - } - - - - }//end switch - - glEnd(); - }//end for loop - - CTerrain* m_Terrain = g_Game->GetWorld()->GetTerrain(); - CEntity* tempHandle = results[0]; - glBegin(GL_LINE_LOOP); - - int width = m_Terrain->GetVerticesPerSide()*4; - glVertex3f( 0, tempHandle->GetAnchorLevel( 0, 0 ) + 0.25f, 0 ); - glVertex3f( width, tempHandle->GetAnchorLevel( width, 0 ) + 0.25f, 0 ); - glVertex3f( width, tempHandle->GetAnchorLevel(width,width ) + 0.25f,width ); - glVertex3f( 0, tempHandle->GetAnchorLevel( 0, width ) + 0.25f, width ); - glEnd(); - - //---------------------- -} -#endif - - void TerrainOverlay::RenderOverlays() { if (g_TerrainOverlayList.size() == 0) return; glEnable(GL_BLEND); glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA); glDepthMask(GL_FALSE); // To ensure that outlines are drawn on top of the terrain correctly (and // don't Z-fight and flicker nastily), draw them as QUADS with the LINE // PolygonMode, and use PolygonOffset to pull them towards the camera. // (See e.g. http://www.opengl.org/resources/faq/technical/polygonoffset.htm) glPolygonOffset(-1.f, -1.f); glEnable(GL_POLYGON_OFFSET_LINE); glDisable(GL_TEXTURE_2D); std::for_each(g_TerrainOverlayList.begin(), g_TerrainOverlayList.end(), render1st()); // Clean up state changes glEnable(GL_CULL_FACE); glEnable(GL_DEPTH_TEST); glDisable(GL_POLYGON_OFFSET_LINE); glPolygonMode(GL_FRONT_AND_BACK, GL_FILL); glDepthMask(GL_TRUE); glDisable(GL_BLEND); //Kai: invoking the auxiliary function to draw out entity edges //RenderEntityEdges(); } ////////////////////////////////////////////////////////////////////////// void TerrainOverlay::StartRender() { } void TerrainOverlay::EndRender() { } void TerrainOverlay::GetTileExtents( ssize_t& min_i_inclusive, ssize_t& min_j_inclusive, ssize_t& max_i_inclusive, ssize_t& max_j_inclusive) { // Default to whole map min_i_inclusive = min_j_inclusive = 0; max_i_inclusive = max_j_inclusive = m_Terrain->GetTilesPerSide()-1; } void TerrainOverlay::Render() { m_Terrain = g_Game->GetWorld()->GetTerrain(); StartRender(); ssize_t min_i, min_j, max_i, max_j; GetTileExtents(min_i, min_j, max_i, max_j); // Clamp the min to 0, but the max to -1 - so tile -1 can never be rendered, // but if unclamped_max<0 then no tiles at all will be rendered. And the same // for the upper limit. min_i = clamp(min_i, ssize_t(0), m_Terrain->GetTilesPerSide()); min_j = clamp(min_j, ssize_t(0), m_Terrain->GetTilesPerSide()); max_i = clamp(max_i, ssize_t(-1), m_Terrain->GetTilesPerSide()-1); max_j = clamp(max_j, ssize_t(-1), m_Terrain->GetTilesPerSide()-1); for (m_j = min_j; m_j <= max_j; ++m_j) for (m_i = min_i; m_i <= max_i; ++m_i) ProcessTile(m_i, m_j); EndRender(); } void TerrainOverlay::RenderTile(const CColor& colour, bool draw_hidden) { RenderTile(colour, draw_hidden, m_i, m_j); } void TerrainOverlay::RenderTile(const CColor& colour, bool draw_hidden, ssize_t i, ssize_t j) { // TODO: if this is unpleasantly slow, make it much more efficient // (e.g. buffering data and making a single draw call? or at least // far fewer calls than it makes now) if (draw_hidden) { glDisable(GL_DEPTH_TEST); glDisable(GL_CULL_FACE); } else { glEnable(GL_DEPTH_TEST); glEnable(GL_CULL_FACE); } glPolygonMode(GL_FRONT_AND_BACK, GL_FILL); CVector3D pos; glBegin(GL_QUADS); glColor4fv(colour.FloatArray()); m_Terrain->CalcPosition(i, j, pos); glVertex3fv(pos.GetFloatArray()); m_Terrain->CalcPosition(i+1, j, pos); glVertex3fv(pos.GetFloatArray()); m_Terrain->CalcPosition(i+1, j+1, pos); glVertex3fv(pos.GetFloatArray()); m_Terrain->CalcPosition(i, j+1, pos); glVertex3fv(pos.GetFloatArray()); glEnd(); } void TerrainOverlay::RenderTileOutline(const CColor& colour, int line_width, bool draw_hidden) { RenderTileOutline(colour, line_width, draw_hidden, m_i, m_j); } void TerrainOverlay::RenderTileOutline(const CColor& colour, int line_width, bool draw_hidden, ssize_t i, ssize_t j) { if (draw_hidden) { glDisable(GL_DEPTH_TEST); glDisable(GL_CULL_FACE); } else { glEnable(GL_DEPTH_TEST); glEnable(GL_CULL_FACE); } glPolygonMode(GL_FRONT_AND_BACK, GL_LINE); if (line_width != 1) glLineWidth((float)line_width); CVector3D pos; glBegin(GL_QUADS); glColor4fv(colour.FloatArray()); m_Terrain->CalcPosition(i, j, pos); glVertex3fv(pos.GetFloatArray()); m_Terrain->CalcPosition(i+1, j, pos); glVertex3fv(pos.GetFloatArray()); m_Terrain->CalcPosition(i+1, j+1, pos); glVertex3fv(pos.GetFloatArray()); m_Terrain->CalcPosition(i, j+1, pos); glVertex3fv(pos.GetFloatArray()); glEnd(); if (line_width != 1) glLineWidth(1.0f); } Index: ps/trunk/source/maths/FixedVector2D.h =================================================================== --- ps/trunk/source/maths/FixedVector2D.h (revision 7483) +++ ps/trunk/source/maths/FixedVector2D.h (revision 7484) @@ -1,135 +1,173 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #ifndef INCLUDED_FIXED_VECTOR2D #define INCLUDED_FIXED_VECTOR2D #include "maths/Fixed.h" #include "maths/Sqrt.h" class CFixedVector2D { private: typedef CFixed_23_8 fixed; public: fixed X, Y; CFixedVector2D() { } CFixedVector2D(fixed X, fixed Y) : X(X), Y(Y) { } /// Vector equality bool operator==(const CFixedVector2D& v) const { return (X == v.X && Y == v.Y); } + /// Vector inequality + bool operator!=(const CFixedVector2D& v) const + { + return (X != v.X || Y != v.Y); + } + /// Vector addition CFixedVector2D operator+(const CFixedVector2D& v) const { return CFixedVector2D(X + v.X, Y + v.Y); } /// Vector subtraction CFixedVector2D operator-(const CFixedVector2D& v) const { return CFixedVector2D(X - v.X, Y - v.Y); } /// Negation CFixedVector2D operator-() const { return CFixedVector2D(-X, -Y); } /// Vector addition CFixedVector2D& operator+=(const CFixedVector2D& v) { *this = *this + v; return *this; } /// Vector subtraction CFixedVector2D& operator-=(const CFixedVector2D& v) { *this = *this - v; return *this; } /// Scalar multiplication by an integer CFixedVector2D operator*(int n) const { return CFixedVector2D(X*n, Y*n); } /** * Multiply by a CFixed. Likely to overflow if both numbers are large, * so we use an ugly name instead of operator* to make it obvious. */ CFixedVector2D Multiply(fixed n) const { return CFixedVector2D(X.Multiply(n), Y.Multiply(n)); } /** * Returns the length of the vector. * Will not overflow if the result can be represented as type 'fixed'. */ fixed Length() const { // Do intermediate calculations with 64-bit ints to avoid overflows i64 x = (i64)X.GetInternalValue(); i64 y = (i64)Y.GetInternalValue(); u64 d2 = (u64)(x * x + y * y); u32 d = isqrt64(d2); fixed r; r.SetInternalValue((i32)d); return r; } + bool IsZero() const + { + return (X.IsZero() && Y.IsZero()); + } + /** * Normalize the vector so that length is close to 1. * If length is 0, does nothing. * WARNING: The fixed-point numbers only have 8-bit fractional parts, so * a normalized vector will be very imprecise. */ void Normalize() { - fixed l = Length(); - if (!l.IsZero()) + if (!IsZero()) { + fixed l = Length(); X = X / l; Y = Y / l; } } /** + * Normalize the vector so that length is close to n. + * If length is 0, does nothing. + */ + void Normalize(fixed n) + { + if (n.IsZero()) + { + X = Y = fixed::FromInt(0); + return; + } + + fixed l = Length(); + // TODO: work out whether this is giving decent precision + fixed d = l / n; + if (!d.IsZero()) + { + X = X / d; + Y = Y / d; + } + } + + /** * Compute the dot product of this vector with another. */ fixed Dot(const CFixedVector2D& v) { i64 x = (i64)X.GetInternalValue() * (i64)v.X.GetInternalValue(); i64 y = (i64)Y.GetInternalValue() * (i64)v.Y.GetInternalValue(); i64 sum = x + y; fixed ret; ret.SetInternalValue((i32)(sum >> fixed::fract_bits)); return ret; } + + CFixedVector2D Perpendicular() + { + return CFixedVector2D(Y, -X); + } }; #endif // INCLUDED_FIXED_VECTOR2D Index: ps/trunk/binaries/data/mods/public/gui/session_new/selection.js =================================================================== --- ps/trunk/binaries/data/mods/public/gui/session_new/selection.js (revision 7483) +++ ps/trunk/binaries/data/mods/public/gui/session_new/selection.js (revision 7484) @@ -1,88 +1,101 @@ var g_ActiveSelectionColour = { r:1, g:1, b:1, a:1 }; var g_HighlightSelectionColour = { r:1, g:1, b:1, a:0.5 }; var g_InactiveSelectionColour = { r:1, g:1, b:1, a:0 }; function _setHighlight(ents, colour) { Engine.GuiInterfaceCall("SetSelectionHighlight", { "entities":ents, "colour":colour }); } +function _setMotionOverlay(ents, enabled) +{ + Engine.GuiInterfaceCall("SetMotionDebugOverlay", { "entities":ents, "enabled":enabled }); +} + function EntitySelection() { this.selected = {}; // { id: 1, id: 1, ... } for each selected entity ID 'id' this.highlighted = {}; // { id: 1, ... } for mouseover-highlighted entity IDs + this.motionDebugOverlay = false; } EntitySelection.prototype.toggle = function(ent) { if (this.selected[ent]) { _setHighlight([ent], g_InactiveSelectionColour); + _setMotionOverlay([ent], false); delete this.selected[ent]; } else { _setHighlight([ent], g_ActiveSelectionColour); + _setMotionOverlay([ent], this.motionDebugOverlay); this.selected[ent] = 1; } }; EntitySelection.prototype.addList = function(ents) { var added = []; for each (var ent in ents) { if (!this.selected[ent]) { added.push(ent); this.selected[ent] = 1; } } _setHighlight(added, g_ActiveSelectionColour); + _setMotionOverlay(added, this.motionDebugOverlay); }; EntitySelection.prototype.reset = function() { _setHighlight(this.toList(), g_InactiveSelectionColour); + _setMotionOverlay(this.toList(), false); this.selected = {}; }; EntitySelection.prototype.toList = function() { var ents = []; for (var ent in this.selected) ents.push(+ent); // convert from string to number and push return ents; }; EntitySelection.prototype.setHighlightList = function(ents) { var removed = []; var added = []; // Remove highlighting for the old units (excluding ones that are actively selected too) for (var ent in this.highlighted) if (!this.selected[ent]) removed.push(ent); // Add new highlighting for each (var ent in ents) if (!this.selected[ent]) added.push(ent); _setHighlight(removed, g_InactiveSelectionColour); _setHighlight(added, g_HighlightSelectionColour); // TODO: this could be a bit more efficient by only changing the ones that // have entered/left the highlight list // Store the new list this.highlighted = {}; for each (var ent in ents) this.highlighted[ent] = 1; }; +EntitySelection.prototype.SetMotionDebugOverlay = function(enabled) +{ + this.motionDebugOverlay = enabled; + _setMotionOverlay(this.toList(), enabled); +}; var g_Selection = new EntitySelection(); - - Index: ps/trunk/binaries/data/mods/public/simulation/components/GuiInterface.js =================================================================== --- ps/trunk/binaries/data/mods/public/simulation/components/GuiInterface.js (revision 7483) +++ ps/trunk/binaries/data/mods/public/simulation/components/GuiInterface.js (revision 7484) @@ -1,255 +1,266 @@ function GuiInterface() {} GuiInterface.prototype.Schema = ""; GuiInterface.prototype.Init = function() { // TODO: need to not serialise this value this.placementEntity = undefined; // = undefined or [templateName, entityID] }; GuiInterface.prototype.GetSimulationState = function(player) { var ret = { "players": [] }; var cmpPlayerMan = Engine.QueryInterface(SYSTEM_ENTITY, IID_PlayerManager); var n = cmpPlayerMan.GetNumPlayers(); for (var i = 0; i < n; ++i) { var playerEnt = cmpPlayerMan.GetPlayerByID(i); var cmpPlayer = Engine.QueryInterface(playerEnt, IID_Player); var playerData = { "popCount": cmpPlayer.GetPopulationCount(), "popLimit": cmpPlayer.GetPopulationLimit(), "resourceCounts": cmpPlayer.GetResourceCounts() }; ret.players.push(playerData); } return ret; }; GuiInterface.prototype.GetEntityState = function(player, ent) { var cmpTempMan = Engine.QueryInterface(SYSTEM_ENTITY, IID_TemplateManager); // All units must have a template; if not then it's a nonexistent entity id var template = cmpTempMan.GetCurrentTemplateName(ent); if (!template) return null; var ret = { "id": ent, "template": template } var cmpPosition = Engine.QueryInterface(ent, IID_Position); if (cmpPosition) { ret.position = cmpPosition.GetPosition(); } var cmpHealth = Engine.QueryInterface(ent, IID_Health); if (cmpHealth) { ret.hitpoints = cmpHealth.GetHitpoints(); ret.maxHitpoints = cmpHealth.GetMaxHitpoints(); } var cmpAttack = Engine.QueryInterface(ent, IID_Attack); if (cmpAttack) { ret.attack = cmpAttack.GetAttackStrengths(); } var cmpArmour = Engine.QueryInterface(ent, IID_DamageReceiver); if (cmpArmour) { ret.armour = cmpArmour.GetArmourStrengths(); } var cmpBuilder = Engine.QueryInterface(ent, IID_Builder); if (cmpBuilder) { ret.buildEntities = cmpBuilder.GetEntitiesList(); } var cmpTrainingQueue = Engine.QueryInterface(ent, IID_TrainingQueue); if (cmpTrainingQueue) { ret.training = { "entities": cmpTrainingQueue.GetEntitiesList(), "queue": cmpTrainingQueue.GetQueue(), }; } var cmpFoundation = Engine.QueryInterface(ent, IID_Foundation); if (cmpFoundation) { ret.foundation = { "progress": cmpFoundation.GetBuildPercentage() }; } var cmpOwnership = Engine.QueryInterface(ent, IID_Ownership); if (cmpOwnership) { ret.player = cmpOwnership.GetOwner(); } var cmpResourceSupply = Engine.QueryInterface(ent, IID_ResourceSupply); if (cmpResourceSupply) { ret.resourceSupply = { "max": cmpResourceSupply.GetMaxAmount(), "amount": cmpResourceSupply.GetCurrentAmount(), "type": cmpResourceSupply.GetType() }; } var cmpResourceGatherer = Engine.QueryInterface(ent, IID_ResourceGatherer); if (cmpResourceGatherer) { ret.resourceGatherRates = cmpResourceGatherer.GetGatherRates(); } return ret; }; GuiInterface.prototype.GetTemplateData = function(player, name) { var cmpTempMan = Engine.QueryInterface(SYSTEM_ENTITY, IID_TemplateManager); var template = cmpTempMan.GetTemplate(name); if (!template) return null; var ret = {}; if (template.Identity) { ret.name = { "specific": (template.Identity.SpecificName || template.Identity.GenericName), "generic": template.Identity.GenericName }; ret.icon_cell = template.Identity.IconCell; } if (template.Cost) { ret.cost = {}; if (template.Cost.Resources.food) ret.cost.food = +template.Cost.Resources.food; if (template.Cost.Resources.wood) ret.cost.wood = +template.Cost.Resources.wood; if (template.Cost.Resources.stone) ret.cost.stone = +template.Cost.Resources.stone; if (template.Cost.Resources.metal) ret.cost.metal = +template.Cost.Resources.metal; } return ret; }; GuiInterface.prototype.SetSelectionHighlight = function(player, cmd) { for each (var ent in cmd.entities) { var cmpSelectable = Engine.QueryInterface(ent, IID_Selectable); if (cmpSelectable) cmpSelectable.SetSelectionHighlight(cmd.colour); } }; /** * Display the building placement preview. * cmd.template is the name of the entity template, or "" to disable the preview. * cmd.x, cmd.z, cmd.angle give the location. * Returns true if the placement is okay (everything is valid and the entity is not obstructed by others). */ GuiInterface.prototype.SetBuildingPlacementPreview = function(player, cmd) { // See if we're changing template if (!this.placementEntity || this.placementEntity[0] != cmd.template) { // Destroy the old preview if there was one if (this.placementEntity) Engine.DestroyEntity(this.placementEntity[1]); // Load the new template if (cmd.template == "") { this.placementEntity = undefined; } else { this.placementEntity = [cmd.template, Engine.AddLocalEntity("preview|" + cmd.template)]; } } if (this.placementEntity) { // Move the preview into the right location var pos = Engine.QueryInterface(this.placementEntity[1], IID_Position); if (pos) { pos.JumpTo(cmd.x, cmd.z); pos.SetYRotation(cmd.angle); } // Check whether it's obstructed by other entities var cmpObstruction = Engine.QueryInterface(this.placementEntity[1], IID_Obstruction); var colliding = (cmpObstruction && cmpObstruction.CheckCollisions()); // Set it to a red shade if this is an obstructed location var cmpVisual = Engine.QueryInterface(this.placementEntity[1], IID_Visual); if (cmpVisual) { if (colliding) cmpVisual.SetShadingColour(1.4, 0.4, 0.4, 1); else cmpVisual.SetShadingColour(1, 1, 1, 1); } if (!colliding) return true; } return false; }; GuiInterface.prototype.SetPathfinderDebugOverlay = function(player, enabled) { var cmpPathfinder = Engine.QueryInterface(SYSTEM_ENTITY, IID_Pathfinder); cmpPathfinder.SetDebugOverlay(enabled); }; GuiInterface.prototype.SetObstructionDebugOverlay = function(player, enabled) { var cmpObstructionManager = Engine.QueryInterface(SYSTEM_ENTITY, IID_ObstructionManager); cmpObstructionManager.SetDebugOverlay(enabled); }; +GuiInterface.prototype.SetMotionDebugOverlay = function(player, data) +{ + for each (var ent in data.entities) + { + var cmpUnitMotion = Engine.QueryInterface(ent, IID_UnitMotion); + if (cmpUnitMotion) + cmpUnitMotion.SetDebugOverlay(data.enabled); + } +}; + // List the GuiInterface functions that can be safely called by GUI scripts. // (GUI scripts are non-deterministic and untrusted, so these functions must be // appropriately careful. They are called with a first argument "player", which is // trusted and indicates the player associated with the current client; no data should // be returned unless this player is meant to be able to see it.) var exposedFunctions = { "GetSimulationState": 1, "GetEntityState": 1, "GetTemplateData": 1, "SetSelectionHighlight": 1, "SetBuildingPlacementPreview": 1, "SetPathfinderDebugOverlay": 1, - "SetObstructionDebugOverlay": 1 + "SetObstructionDebugOverlay": 1, + "SetMotionDebugOverlay": 1, }; GuiInterface.prototype.ScriptCall = function(player, name, args) { if (exposedFunctions[name]) return this[name](player, args); else throw new Error("Invalid GuiInterface Call name \""+name+"\""); }; Engine.RegisterComponentType(IID_GuiInterface, "GuiInterface", GuiInterface); Index: ps/trunk/binaries/data/mods/public/simulation/components/Builder.js =================================================================== --- ps/trunk/binaries/data/mods/public/simulation/components/Builder.js (revision 7483) +++ ps/trunk/binaries/data/mods/public/simulation/components/Builder.js (revision 7484) @@ -1,63 +1,63 @@ function Builder() {} Builder.prototype.Schema = "Allows the unit to construct and repair buildings." + "" + "1.0" + "" + "\n structures/{civ}_barracks\n structures/{civ}_civil_centre\n structures/celt_sb1\n " + "" + "" + "" + "" + "" + "" + "" + ""; Builder.prototype.Init = function() { }; Builder.prototype.GetEntitiesList = function() { var string = this.template.Entities; // Replace the "{civ}" codes with this entity's civ ID var cmpIdentity = Engine.QueryInterface(this.entity, IID_Identity); if (cmpIdentity) string = string.replace(/\{civ\}/g, cmpIdentity.GetCiv()); return string.split(/\s+/); }; Builder.prototype.GetRange = function() { - return { "max": 16, "min": 0 }; + return { "max": 2, "min": 0 }; // maybe this should depend on the unit or target or something? } /** * Build/repair the target entity. This should only be called after a successful range check. * It should be called at a rate of once per second. */ Builder.prototype.PerformBuilding = function(target) { var rate = +this.template.Rate; // If it's a foundation, then build it var cmpFoundation = Engine.QueryInterface(target, IID_Foundation); if (cmpFoundation) { var finished = cmpFoundation.Build(this.entity, rate); return { "finished": finished }; } else { // TODO: do some kind of repairing return { "finished": true }; } }; Engine.RegisterComponentType(IID_Builder, "Builder", Builder); Index: ps/trunk/binaries/data/mods/public/simulation/templates/template_structure_economic_mill.xml =================================================================== --- ps/trunk/binaries/data/mods/public/simulation/templates/template_structure_economic_mill.xml (revision 7483) +++ ps/trunk/binaries/data/mods/public/simulation/templates/template_structure_economic_mill.xml (revision 7484) @@ -1,28 +1,31 @@ Mill 52 16 100 800 10.0 40.0 15.0 structures/fndn_3x3.xml 8.0 + + + Index: ps/trunk/binaries/data/mods/public/simulation/templates/template_structure.xml =================================================================== --- ps/trunk/binaries/data/mods/public/simulation/templates/template_structure.xml (revision 7483) +++ ps/trunk/binaries/data/mods/public/simulation/templates/template_structure.xml (revision 7484) @@ -1,28 +1,27 @@ Structure PortraitSheet structure 10 0 0 0 0 vanish 10.0 42.0 10.0 - Index: ps/trunk/binaries/data/mods/public/gui/session_new/session.xml =================================================================== --- ps/trunk/binaries/data/mods/public/gui/session_new/session.xml (revision 7483) +++ ps/trunk/binaries/data/mods/public/gui/session_new/session.xml (revision 7484) @@ -1,267 +1,272 @@