Index: binaries/data/mods/public/gui/gamesetup/gamesetup.js =================================================================== --- binaries/data/mods/public/gui/gamesetup/gamesetup.js +++ binaries/data/mods/public/gui/gamesetup/gamesetup.js @@ -412,7 +412,8 @@ "nomad", "disableTreasures", "exploreMap", - "revealMap" + "revealMap", + "experimentalLos", ] }, { @@ -832,6 +833,20 @@ return obj; }, {}), { + "experimentalLos": { + "title": () => translate("Experimental vision"), + "tooltip": () => translate("Toogle whenever terrain should block vision."), + "default": () => false, + "defined": () => g_GameAttributes.ExperimentalLos !== undefined, + "get": () => g_GameAttributes.ExperimentalLos, + "set": checked => { + g_GameAttributes.ExperimentalLos = checked; + }, + "hidden": () => false, + "enabled": () => !g_GameAttributes.settings.RevealMap, + "initOrder": 1000 + + }, "regicideGarrison": { "title": () => translate("Hero Garrison"), "tooltip": () => translate("Toggle whether heroes can be garrisoned."), @@ -870,8 +885,10 @@ "set": checked => { g_GameAttributes.settings.RevealMap = checked; - if (checked) + if (checked) { g_Checkboxes.exploreMap.set(true); + g_Checkboxes.experimentalLos.set(false); + } }, "enabled": () => g_GameAttributes.mapType != "scenario", "initOrder": 1000 @@ -2357,6 +2374,10 @@ // Used for identifying rated game reports for the lobby g_GameAttributes.matchID = Engine.GetMatchID(); + // Set default LOS implementation + if (g_GameAttributes.ExperimentalLos === undefined) + g_GameAttributes.ExperimentalLos = false; + if (g_IsNetworked) { Engine.SetNetworkGameAttributes(g_GameAttributes); Index: libraries/win32/boost/include/boost/dynamic_bitset.hpp =================================================================== --- /dev/null +++ libraries/win32/boost/include/boost/dynamic_bitset.hpp @@ -0,0 +1,17 @@ +// ----------------------------------------------------------- +// +// Copyright (c) 2001-2002 Chuck Allison and Jeremy Siek +// Copyright (c) 2003-2004, 2008 Gennaro Prota +// +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +// +// ----------------------------------------------------------- + +#ifndef BOOST_DYNAMIC_BITSET_HPP +#define BOOST_DYNAMIC_BITSET_HPP + +#include "boost/dynamic_bitset/dynamic_bitset.hpp" + +#endif // include guard Index: libraries/win32/boost/include/boost/dynamic_bitset/config.hpp =================================================================== --- /dev/null +++ libraries/win32/boost/include/boost/dynamic_bitset/config.hpp @@ -0,0 +1,72 @@ +// ----------------------------------------------------------- +// +// Copyright (c) 2001-2002 Chuck Allison and Jeremy Siek +// Copyright (c) 2003-2006, 2008 Gennaro Prota +// +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +// +// ----------------------------------------------------------- + +#ifndef BOOST_DYNAMIC_BITSET_CONFIG_HPP_GP_20040424 +#define BOOST_DYNAMIC_BITSET_CONFIG_HPP_GP_20040424 + +#include "boost/config.hpp" +#include "boost/detail/workaround.hpp" + +// support for pre 3.0 libstdc++ - thanks Phil Edwards! +#if defined (__STL_CONFIG_H) && !defined (__STL_USE_NEW_IOSTREAMS) +# define BOOST_OLD_IOSTREAMS +#endif + +// no-op function to workaround gcc bug c++/8419 +// +namespace boost { namespace detail { + template T make_non_const(T t) { return t; } +}} + +#if defined(__GNUC__) +# define BOOST_DYNAMIC_BITSET_WRAP_CONSTANT(expr) \ + (boost::detail::make_non_const(expr)) +#else +# define BOOST_DYNAMIC_BITSET_WRAP_CONSTANT(expr) (expr) +#endif + +// +#if (defined __BORLANDC__ && BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))) \ + || (defined BOOST_NO_MEMBER_TEMPLATE_FRIENDS) +#define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS +#endif + +// if we can't use friends then we simply expose private members +// +#if defined(BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS) +#define BOOST_DYNAMIC_BITSET_PRIVATE public +#else +#define BOOST_DYNAMIC_BITSET_PRIVATE private +#endif + +// A couple of macros to cope with libraries without locale +// support. The first macro must be used to declare a reference +// to a ctype facet. The second one to widen a char by using +// that ctype object. If facets and locales aren't available +// the first macro is a no-op and the second one just expands +// to its parameter c. +// +#if defined (BOOST_USE_FACET) + +#define BOOST_DYNAMIC_BITSET_CTYPE_FACET(ch, name, loc) \ + const std::ctype & name = \ + BOOST_USE_FACET(std::ctype, loc) /**/ + +#define BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, c) \ + (fac.widen(c)) +#else + +#define BOOST_DYNAMIC_BITSET_CTYPE_FACET(ch, name, loc) /**/ +#define BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, c) c + +#endif + +#endif // include guard Index: libraries/win32/boost/include/boost/dynamic_bitset/detail/dynamic_bitset.hpp =================================================================== --- /dev/null +++ libraries/win32/boost/include/boost/dynamic_bitset/detail/dynamic_bitset.hpp @@ -0,0 +1,304 @@ +// ----------------------------------------------------------- +// +// Copyright (c) 2001-2002 Chuck Allison and Jeremy Siek +// Copyright (c) 2003-2006, 2008 Gennaro Prota +// Copyright (c) 2014 Glen Joseph Fernandes +// (glenjofe@gmail.com) +// Copyright (c) 2018 Evgeny Shulgin +// Copyright (c) 2019 Andrey Semashev +// +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +// +// ----------------------------------------------------------- + +#ifndef BOOST_DETAIL_DYNAMIC_BITSET_HPP +#define BOOST_DETAIL_DYNAMIC_BITSET_HPP + +#include +#include +#include "boost/config.hpp" +#include "boost/detail/workaround.hpp" + +#if ((defined(BOOST_MSVC) && (BOOST_MSVC >= 1600)) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64)) +#include +#endif + +namespace boost { + + namespace detail { + namespace dynamic_bitset_impl { + + // Gives (read-)access to the object representation + // of an object of type T (3.9p4). CANNOT be used + // on a base sub-object + // + template + inline const unsigned char * object_representation (T* p) + { + return static_cast(static_cast(p)); + } + + template + struct shifter + { + static void left_shift(T & v) { + amount >= width ? (v = 0) + : (v >>= BOOST_DYNAMIC_BITSET_WRAP_CONSTANT(amount)); + } + }; + + // ------- count function implementation -------------- + + typedef unsigned char byte_type; + + // These two entities + // + // enum mode { access_by_bytes, access_by_blocks }; + // template struct mode_to_type {}; + // + // were removed, since the regression logs (as of 24 Aug 2008) + // showed that several compilers had troubles with recognizing + // + // const mode m = access_by_bytes + // + // as a constant expression + // + // * So, we'll use bool, instead of enum *. + // + template + struct value_to_type + { + value_to_type() {} + }; + const bool access_by_bytes = true; + const bool access_by_blocks = false; + + + // the table: wrapped in a class template, so + // that it is only instantiated if/when needed + // + template + struct count_table { static const byte_type table[]; }; + + template <> + struct count_table { /* no table */ }; + + + const unsigned int table_width = 8; + template + const byte_type count_table::table[] = + { + // Automatically generated by GPTableGen.exe v.1.0 + // + 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 + }; + + + // Some platforms have fast popcount operation, that allow us to implement + // counting bits much more efficiently + // + template + BOOST_FORCEINLINE std::size_t popcount(ValueType value) BOOST_NOEXCEPT + { + std::size_t num = 0u; + while (value) { + num += count_table<>::table[value & ((1u<>= table_width; + } + return num; + } + +#if (((defined(BOOST_MSVC) && (BOOST_MSVC >= 1600)) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64))) \ + && (defined(__POPCNT__) || defined(__AVX__)) + + template <> + BOOST_FORCEINLINE std::size_t popcount(unsigned short value) BOOST_NOEXCEPT + { + return static_cast(__popcnt16(value)); + } + + template <> + BOOST_FORCEINLINE std::size_t popcount(unsigned int value) BOOST_NOEXCEPT + { + return static_cast(__popcnt(value)); + } + + template <> + BOOST_FORCEINLINE std::size_t popcount(unsigned __int64 value) BOOST_NOEXCEPT + { +#if defined(_M_X64) + return static_cast(__popcnt64(value)); +#else + return static_cast(__popcnt(static_cast< unsigned int >(value))) + static_cast(__popcnt(static_cast< unsigned int >(value >> 32))); +#endif + } + +#elif defined(BOOST_GCC) || defined(__clang__) || (defined(BOOST_INTEL) && defined(__GNUC__)) + + // Note: gcc builtins are implemented by compiler runtime when the target CPU may not support the necessary instructions + template <> + BOOST_FORCEINLINE std::size_t popcount(unsigned short value) BOOST_NOEXCEPT + { + return static_cast(__builtin_popcount(static_cast(value))); + } + + template <> + BOOST_FORCEINLINE std::size_t popcount(unsigned int value) BOOST_NOEXCEPT + { + return static_cast(__builtin_popcount(value)); + } + + template <> + BOOST_FORCEINLINE std::size_t popcount(unsigned long value) BOOST_NOEXCEPT + { + return static_cast(__builtin_popcountl(value)); + } + + template <> + BOOST_FORCEINLINE std::size_t popcount(boost::ulong_long_type value) BOOST_NOEXCEPT + { + return static_cast(__builtin_popcountll(value)); + } + +#endif + + // overload for access by blocks + // + template + inline std::size_t do_count(Iterator first, std::size_t length, ValueType, + value_to_type*) + { + std::size_t num1 = 0u, num2 = 0u; + while (length >= 2u) { + num1 += popcount(*first); + ++first; + num2 += popcount(*first); + ++first; + length -= 2u; + } + + if (length > 0u) + num1 += popcount(*first); + + return num1 + num2; + } + + // overload for access by bytes + // + template + inline std::size_t do_count(Iterator first, std::size_t length, + int /*dummy param*/, + value_to_type*) + { + if (length > 0u) { + const byte_type* p = object_representation(&*first); + length *= sizeof(*first); + + return do_count(p, length, static_cast(0u), + static_cast< value_to_type* >(0)); + } + + return 0u; + } + + // ------------------------------------------------------- + + + // Some library implementations simply return a dummy + // value such as + // + // size_type(-1) / sizeof(T) + // + // from vector<>::max_size. This tries to get more + // meaningful info. + // + template + inline typename T::size_type vector_max_size_workaround(const T & v) + BOOST_NOEXCEPT + { + typedef typename T::allocator_type allocator_type; + + const allocator_type& alloc = v.get_allocator(); + +#if !defined(BOOST_NO_CXX11_ALLOCATOR) + typedef std::allocator_traits allocator_traits; + + const typename allocator_traits::size_type alloc_max = + allocator_traits::max_size(alloc); +#else + const typename allocator_type::size_type alloc_max = alloc.max_size(); +#endif + + const typename T::size_type container_max = v.max_size(); + + return alloc_max < container_max ? alloc_max : container_max; + } + + // for static_asserts + template + struct allowed_block_type { + enum { value = T(-1) > 0 }; // ensure T has no sign + }; + + template <> + struct allowed_block_type { + enum { value = false }; + }; + + + template + struct is_numeric { + enum { value = false }; + }; + +# define BOOST_dynamic_bitset_is_numeric(x) \ + template<> \ + struct is_numeric< x > { \ + enum { value = true }; \ + } /**/ + + BOOST_dynamic_bitset_is_numeric(bool); + BOOST_dynamic_bitset_is_numeric(char); + +#if !defined(BOOST_NO_INTRINSIC_WCHAR_T) + BOOST_dynamic_bitset_is_numeric(wchar_t); +#endif + + BOOST_dynamic_bitset_is_numeric(signed char); + BOOST_dynamic_bitset_is_numeric(short int); + BOOST_dynamic_bitset_is_numeric(int); + BOOST_dynamic_bitset_is_numeric(long int); + + BOOST_dynamic_bitset_is_numeric(unsigned char); + BOOST_dynamic_bitset_is_numeric(unsigned short); + BOOST_dynamic_bitset_is_numeric(unsigned int); + BOOST_dynamic_bitset_is_numeric(unsigned long); + +#if defined(BOOST_HAS_LONG_LONG) + BOOST_dynamic_bitset_is_numeric(::boost::long_long_type); + BOOST_dynamic_bitset_is_numeric(::boost::ulong_long_type); +#endif + + // intentionally omitted + //BOOST_dynamic_bitset_is_numeric(float); + //BOOST_dynamic_bitset_is_numeric(double); + //BOOST_dynamic_bitset_is_numeric(long double); + +#undef BOOST_dynamic_bitset_is_numeric + + } // dynamic_bitset_impl + } // namespace detail + +} // namespace boost + +#endif // include guard + Index: libraries/win32/boost/include/boost/dynamic_bitset/detail/lowest_bit.hpp =================================================================== --- /dev/null +++ libraries/win32/boost/include/boost/dynamic_bitset/detail/lowest_bit.hpp @@ -0,0 +1,39 @@ +// ----------------------------------------------------------- +// lowest_bit.hpp +// +// Position of the lowest bit 'on' +// +// Copyright (c) 2003-2004, 2008 Gennaro Prota +// +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +// +// ----------------------------------------------------------- + +#ifndef BOOST_LOWEST_BIT_HPP_GP_20030301 +#define BOOST_LOWEST_BIT_HPP_GP_20030301 + +#include "boost/integer/integer_log2.hpp" +#include "boost/assert.hpp" + +namespace boost { +namespace detail { + + template + int lowest_bit(T x) { + + BOOST_ASSERT(x >= 1); // PRE + + // clear all bits on except the rightmost one, + // then calculate the logarithm base 2 + // + return boost::integer_log2( x - ( x & (x-1) ) ); + + } + +} +} + + +#endif // include guard Index: libraries/win32/boost/include/boost/dynamic_bitset/dynamic_bitset.hpp =================================================================== --- /dev/null +++ libraries/win32/boost/include/boost/dynamic_bitset/dynamic_bitset.hpp @@ -0,0 +1,2146 @@ +// ----------------------------------------------------------- +// +// Copyright (c) 2001-2002 Chuck Allison and Jeremy Siek +// Copyright (c) 2003-2006, 2008 Gennaro Prota +// Copyright (c) 2014 Ahmed Charles +// +// Copyright (c) 2014 Glen Joseph Fernandes +// (glenjofe@gmail.com) +// +// Copyright (c) 2014 Riccardo Marcangelo +// Copyright (c) 2018 Evgeny Shulgin +// +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +// +// ----------------------------------------------------------- + +#ifndef BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP +#define BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP + +#include +#include +#include +#include +#include +#include // for CHAR_BIT + +#include "boost/dynamic_bitset/config.hpp" + +#ifndef BOOST_NO_STD_LOCALE +# include +#endif + +#if defined(BOOST_OLD_IOSTREAMS) +# include +# include // for isspace +#else +# include +# include +#endif + +#include "boost/dynamic_bitset_fwd.hpp" +#include "boost/dynamic_bitset/detail/dynamic_bitset.hpp" +#include "boost/dynamic_bitset/detail/lowest_bit.hpp" +#include "boost/detail/iterator.hpp" // used to implement append(Iter, Iter) +#include "boost/move/move.hpp" +#include "boost/limits.hpp" +#include "boost/static_assert.hpp" +#include "boost/utility/addressof.hpp" +#include "boost/detail/no_exceptions_support.hpp" +#include "boost/throw_exception.hpp" +#include "boost/functional/hash/hash.hpp" + + +namespace boost { + +template +class dynamic_bitset +{ + // Portability note: member function templates are defined inside + // this class definition to avoid problems with VC++. Similarly, + // with the member functions of nested classes. + // + // [October 2008: the note above is mostly historical; new versions + // of VC++ are likely able to digest a more drinking form of the + // code; but changing it now is probably not worth the risks...] + + BOOST_STATIC_ASSERT((bool)detail::dynamic_bitset_impl::allowed_block_type::value); + typedef std::vector buffer_type; + +public: + typedef Block block_type; + typedef Allocator allocator_type; + typedef std::size_t size_type; + typedef typename buffer_type::size_type block_width_type; + + BOOST_STATIC_CONSTANT(block_width_type, bits_per_block = (std::numeric_limits::digits)); + BOOST_STATIC_CONSTANT(size_type, npos = static_cast(-1)); + + +public: + + // A proxy class to simulate lvalues of bit type. + // + class reference + { + friend class dynamic_bitset; + + + // the one and only non-copy ctor + reference(block_type & b, block_width_type pos) + :m_block(b), + m_mask( (assert(pos < bits_per_block), + block_type(1) << pos ) + ) + { } + + void operator&(); // left undefined + + public: + + // copy constructor: compiler generated + + operator bool() const { return (m_block & m_mask) != 0; } + bool operator~() const { return (m_block & m_mask) == 0; } + + reference& flip() { do_flip(); return *this; } + + reference& operator=(bool x) { do_assign(x); return *this; } // for b[i] = x + reference& operator=(const reference& rhs) { do_assign(rhs); return *this; } // for b[i] = b[j] + + reference& operator|=(bool x) { if (x) do_set(); return *this; } + reference& operator&=(bool x) { if (!x) do_reset(); return *this; } + reference& operator^=(bool x) { if (x) do_flip(); return *this; } + reference& operator-=(bool x) { if (x) do_reset(); return *this; } + + private: + block_type & m_block; + const block_type m_mask; + + void do_set() { m_block |= m_mask; } + void do_reset() { m_block &= ~m_mask; } + void do_flip() { m_block ^= m_mask; } + void do_assign(bool x) { x? do_set() : do_reset(); } + }; + + typedef bool const_reference; + + // constructors, etc. + dynamic_bitset() : m_num_bits(0) {} + + explicit + dynamic_bitset(const Allocator& alloc); + + explicit + dynamic_bitset(size_type num_bits, unsigned long value = 0, + const Allocator& alloc = Allocator()); + + + // WARNING: you should avoid using this constructor. + // + // A conversion from string is, in most cases, formatting, + // and should be performed by using operator>>. + // + // NOTE: + // Leave the parentheses around std::basic_string::npos. + // g++ 3.2 requires them and probably the standard will - see core issue 325 + // NOTE 2: + // split into two constructors because of bugs in MSVC 6.0sp5 with STLport + + template + dynamic_bitset(const std::basic_string& s, + typename std::basic_string::size_type pos, + typename std::basic_string::size_type n, + size_type num_bits = npos, + const Allocator& alloc = Allocator()) + + :m_bits(alloc), + m_num_bits(0) + { + init_from_string(s, pos, n, num_bits); + } + + template + explicit + dynamic_bitset(const std::basic_string& s, + typename std::basic_string::size_type pos = 0) + + :m_bits(Allocator()), + m_num_bits(0) + { + init_from_string(s, pos, (std::basic_string::npos), + npos); + } + + // The first bit in *first is the least significant bit, and the + // last bit in the block just before *last is the most significant bit. + template + dynamic_bitset(BlockInputIterator first, BlockInputIterator last, + const Allocator& alloc = Allocator()) + + :m_bits(alloc), + m_num_bits(0) + { + using boost::detail::dynamic_bitset_impl::value_to_type; + using boost::detail::dynamic_bitset_impl::is_numeric; + + const value_to_type< + is_numeric::value> selector; + + dispatch_init(first, last, selector); + } + + template + void dispatch_init(T num_bits, unsigned long value, + detail::dynamic_bitset_impl::value_to_type) + { + init_from_unsigned_long(static_cast(num_bits), value); + } + + template + void dispatch_init(T first, T last, + detail::dynamic_bitset_impl::value_to_type) + { + init_from_block_range(first, last); + } + + template + void init_from_block_range(BlockIter first, BlockIter last) + { + assert(m_bits.size() == 0); + m_bits.insert(m_bits.end(), first, last); + m_num_bits = m_bits.size() * bits_per_block; + } + + // copy constructor + dynamic_bitset(const dynamic_bitset& b); + + ~dynamic_bitset(); + + void swap(dynamic_bitset& b); + dynamic_bitset& operator=(const dynamic_bitset& b); + +#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES + dynamic_bitset(dynamic_bitset&& src); + dynamic_bitset& operator=(dynamic_bitset&& src); +#endif // BOOST_NO_CXX11_RVALUE_REFERENCES + + allocator_type get_allocator() const; + + // size changing operations + void resize(size_type num_bits, bool value = false); + void clear(); + void push_back(bool bit); + void pop_back(); + void append(Block block); + + template + void m_append(BlockInputIterator first, BlockInputIterator last, std::input_iterator_tag) + { + std::vector v(first, last); + m_append(v.begin(), v.end(), std::random_access_iterator_tag()); + } + template + void m_append(BlockInputIterator first, BlockInputIterator last, std::forward_iterator_tag) + { + assert(first != last); + block_width_type r = count_extra_bits(); + std::size_t d = boost::detail::distance(first, last); + m_bits.reserve(num_blocks() + d); + if (r == 0) { + for( ; first != last; ++first) + m_bits.push_back(*first); // could use vector<>::insert() + } + else { + m_highest_block() |= (*first << r); + do { + Block b = *first >> (bits_per_block - r); + ++first; + m_bits.push_back(b | (first==last? 0 : *first << r)); + } while (first != last); + } + m_num_bits += bits_per_block * d; + } + template + void append(BlockInputIterator first, BlockInputIterator last) // strong guarantee + { + if (first != last) { + typename detail::iterator_traits::iterator_category cat; + m_append(first, last, cat); + } + } + + + // bitset operations + dynamic_bitset& operator&=(const dynamic_bitset& b); + dynamic_bitset& operator|=(const dynamic_bitset& b); + dynamic_bitset& operator^=(const dynamic_bitset& b); + dynamic_bitset& operator-=(const dynamic_bitset& b); + dynamic_bitset& operator<<=(size_type n); + dynamic_bitset& operator>>=(size_type n); + dynamic_bitset operator<<(size_type n) const; + dynamic_bitset operator>>(size_type n) const; + + // basic bit operations + dynamic_bitset& set(size_type n, size_type len, bool val /* = true */); // default would make it ambiguous + dynamic_bitset& set(size_type n, bool val = true); + dynamic_bitset& set(); + dynamic_bitset& reset(size_type n, size_type len); + dynamic_bitset& reset(size_type n); + dynamic_bitset& reset(); + dynamic_bitset& flip(size_type n, size_type len); + dynamic_bitset& flip(size_type n); + dynamic_bitset& flip(); + bool test(size_type n) const; + bool test_set(size_type n, bool val = true); + bool all() const; + bool any() const; + bool none() const; + dynamic_bitset operator~() const; + size_type count() const BOOST_NOEXCEPT; + + // subscript + reference operator[](size_type pos) { + return reference(m_bits[block_index(pos)], bit_index(pos)); + } + bool operator[](size_type pos) const { return test(pos); } + + unsigned long to_ulong() const; + + size_type size() const BOOST_NOEXCEPT; + size_type num_blocks() const BOOST_NOEXCEPT; + size_type max_size() const BOOST_NOEXCEPT; + bool empty() const BOOST_NOEXCEPT; + size_type capacity() const BOOST_NOEXCEPT; + void reserve(size_type num_bits); + void shrink_to_fit(); + + bool is_subset_of(const dynamic_bitset& a) const; + bool is_proper_subset_of(const dynamic_bitset& a) const; + bool intersects(const dynamic_bitset & a) const; + + // lookup + size_type find_first() const; + size_type find_next(size_type pos) const; + + +#if !defined BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS + // lexicographical comparison + template + friend bool operator==(const dynamic_bitset& a, + const dynamic_bitset& b); + + template + friend bool operator<(const dynamic_bitset& a, + const dynamic_bitset& b); + + template + friend bool oplessthan(const dynamic_bitset& a, + const dynamic_bitset& b); + + + template + friend void to_block_range(const dynamic_bitset& b, + BlockOutputIterator result); + + template + friend void from_block_range(BlockIterator first, BlockIterator last, + dynamic_bitset& result); + + + template + friend std::basic_istream& operator>>(std::basic_istream& is, + dynamic_bitset& b); + + template + friend void to_string_helper(const dynamic_bitset & b, stringT & s, bool dump_all); + + template + friend std::size_t hash_value(const dynamic_bitset& a); +#endif + +public: + // forward declaration for optional zero-copy serialization support + class serialize_impl; + friend class serialize_impl; + +private: + BOOST_STATIC_CONSTANT(block_width_type, ulong_width = std::numeric_limits::digits); + + dynamic_bitset& range_operation(size_type pos, size_type len, + Block (*partial_block_operation)(Block, size_type, size_type), + Block (*full_block_operation)(Block)); + void m_zero_unused_bits(); + bool m_check_invariants() const; + + size_type m_do_find_from(size_type first_block) const; + + block_width_type count_extra_bits() const BOOST_NOEXCEPT { return bit_index(size()); } + static size_type block_index(size_type pos) BOOST_NOEXCEPT { return pos / bits_per_block; } + static block_width_type bit_index(size_type pos) BOOST_NOEXCEPT { return static_cast(pos % bits_per_block); } + static Block bit_mask(size_type pos) BOOST_NOEXCEPT { return Block(1) << bit_index(pos); } + static Block bit_mask(size_type first, size_type last) BOOST_NOEXCEPT + { + Block res = (last == bits_per_block - 1) + ? static_cast(~0) + : ((Block(1) << (last + 1)) - 1); + res ^= (Block(1) << first) - 1; + return res; + } + static Block set_block_bits(Block block, size_type first, + size_type last, bool val) BOOST_NOEXCEPT + { + if (val) + return block | bit_mask(first, last); + else + return block & static_cast(~bit_mask(first, last)); + } + + // Functions for operations on ranges + inline static Block set_block_partial(Block block, size_type first, + size_type last) BOOST_NOEXCEPT + { + return set_block_bits(block, first, last, true); + } + inline static Block set_block_full(Block) BOOST_NOEXCEPT + { + return static_cast(~0); + } + inline static Block reset_block_partial(Block block, size_type first, + size_type last) BOOST_NOEXCEPT + { + return set_block_bits(block, first, last, false); + } + inline static Block reset_block_full(Block) BOOST_NOEXCEPT + { + return 0; + } + inline static Block flip_block_partial(Block block, size_type first, + size_type last) BOOST_NOEXCEPT + { + return block ^ bit_mask(first, last); + } + inline static Block flip_block_full(Block block) BOOST_NOEXCEPT + { + return ~block; + } + + template + void init_from_string(const std::basic_string& s, + typename std::basic_string::size_type pos, + typename std::basic_string::size_type n, + size_type num_bits) + { + assert(pos <= s.size()); + + typedef typename std::basic_string StrT; + typedef typename StrT::traits_type Tr; + + const typename StrT::size_type rlen = (std::min)(n, s.size() - pos); + const size_type sz = ( num_bits != npos? num_bits : rlen); + m_bits.resize(calc_num_blocks(sz)); + m_num_bits = sz; + + + BOOST_DYNAMIC_BITSET_CTYPE_FACET(CharT, fac, std::locale()); + const CharT one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1'); + + const size_type m = num_bits < rlen ? num_bits : rlen; + typename StrT::size_type i = 0; + for( ; i < m; ++i) { + + const CharT c = s[(pos + m - 1) - i]; + + assert( Tr::eq(c, one) + || Tr::eq(c, BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0')) ); + + if (Tr::eq(c, one)) + set(i); + + } + + } + + void init_from_unsigned_long(size_type num_bits, + unsigned long value/*, + const Allocator& alloc*/) + { + + assert(m_bits.size() == 0); + + m_bits.resize(calc_num_blocks(num_bits)); + m_num_bits = num_bits; + + typedef unsigned long num_type; + typedef boost::detail::dynamic_bitset_impl + ::shifter shifter; + + //if (num_bits == 0) + // return; + + // zero out all bits at pos >= num_bits, if any; + // note that: num_bits == 0 implies value == 0 + if (num_bits < static_cast(ulong_width)) { + const num_type mask = (num_type(1) << num_bits) - 1; + value &= mask; + } + + typename buffer_type::iterator it = m_bits.begin(); + for( ; value; shifter::left_shift(value), ++it) { + *it = static_cast(value); + } + + } + + + +BOOST_DYNAMIC_BITSET_PRIVATE: + + bool m_unchecked_test(size_type pos) const; + static size_type calc_num_blocks(size_type num_bits); + + Block& m_highest_block(); + const Block& m_highest_block() const; + + buffer_type m_bits; + size_type m_num_bits; + + + class bit_appender; + friend class bit_appender; + class bit_appender { + // helper for stream >> + // Supplies to the lack of an efficient append at the less + // significant end: bits are actually appended "at left" but + // rearranged in the destructor. From the perspective of + // client code everything works *as if* dynamic_bitset<> had + // an append_at_right() function (eventually throwing the same + // exceptions as push_back) except that the function is in fact + // called bit_appender::do_append(). + // + dynamic_bitset & bs; + size_type n; + Block mask; + Block * current; + + // not implemented + bit_appender(const bit_appender &); + bit_appender & operator=(const bit_appender &); + + public: + bit_appender(dynamic_bitset & r) : bs(r), n(0), mask(0), current(0) {} + ~bit_appender() { + // reverse the order of blocks, shift + // if needed, and then resize + // + std::reverse(bs.m_bits.begin(), bs.m_bits.end()); + const block_width_type offs = bit_index(n); + if (offs) + bs >>= (bits_per_block - offs); + bs.resize(n); // doesn't enlarge, so can't throw + assert(bs.m_check_invariants()); + } + inline void do_append(bool value) { + + if (mask == 0) { + bs.append(Block(0)); + current = &bs.m_highest_block(); + mask = Block(1) << (bits_per_block - 1); + } + + if(value) + *current |= mask; + + mask /= 2; + ++n; + } + size_type get_count() const { return n; } + }; + +}; + +#if !defined BOOST_NO_INCLASS_MEMBER_INITIALIZATION + +template +const typename dynamic_bitset::block_width_type +dynamic_bitset::bits_per_block; + +template +const typename dynamic_bitset::size_type +dynamic_bitset::npos; + +template +const typename dynamic_bitset::block_width_type +dynamic_bitset::ulong_width; + +#endif + +// Global Functions: + +// comparison +template +bool operator!=(const dynamic_bitset& a, + const dynamic_bitset& b); + +template +bool operator<=(const dynamic_bitset& a, + const dynamic_bitset& b); + +template +bool operator>(const dynamic_bitset& a, + const dynamic_bitset& b); + +template +bool operator>=(const dynamic_bitset& a, + const dynamic_bitset& b); + +// stream operators +#ifdef BOOST_OLD_IOSTREAMS +template +std::ostream& operator<<(std::ostream& os, + const dynamic_bitset& b); + +template +std::istream& operator>>(std::istream& is, dynamic_bitset& b); +#else +template +std::basic_ostream& +operator<<(std::basic_ostream& os, + const dynamic_bitset& b); + +template +std::basic_istream& +operator>>(std::basic_istream& is, + dynamic_bitset& b); +#endif + +// bitset operations +template +dynamic_bitset +operator&(const dynamic_bitset& b1, + const dynamic_bitset& b2); + +template +dynamic_bitset +operator|(const dynamic_bitset& b1, + const dynamic_bitset& b2); + +template +dynamic_bitset +operator^(const dynamic_bitset& b1, + const dynamic_bitset& b2); + +template +dynamic_bitset +operator-(const dynamic_bitset& b1, + const dynamic_bitset& b2); + +// namespace scope swap +template +void swap(dynamic_bitset& b1, + dynamic_bitset& b2); + + +template +void +to_string(const dynamic_bitset& b, stringT & s); + +template +void +to_block_range(const dynamic_bitset& b, + BlockOutputIterator result); + + +template +inline void +from_block_range(BlockIterator first, BlockIterator last, + dynamic_bitset& result) +{ + // PRE: distance(first, last) <= numblocks() + std::copy (first, last, result.m_bits.begin()); +} + +//============================================================================= +// dynamic_bitset implementation + + +//----------------------------------------------------------------------------- +// constructors, etc. + +template +dynamic_bitset::dynamic_bitset(const Allocator& alloc) + : m_bits(alloc), m_num_bits(0) +{ + +} + +template +dynamic_bitset:: +dynamic_bitset(size_type num_bits, unsigned long value, const Allocator& alloc) + : m_bits(alloc), + m_num_bits(0) +{ + init_from_unsigned_long(num_bits, value); +} + +// copy constructor +template +inline dynamic_bitset:: +dynamic_bitset(const dynamic_bitset& b) + : m_bits(b.m_bits), m_num_bits(b.m_num_bits) +{ + +} + +template +inline dynamic_bitset:: +~dynamic_bitset() +{ + assert(m_check_invariants()); +} + +template +inline void dynamic_bitset:: +swap(dynamic_bitset& b) // no throw +{ + std::swap(m_bits, b.m_bits); + std::swap(m_num_bits, b.m_num_bits); +} + +template +dynamic_bitset& dynamic_bitset:: +operator=(const dynamic_bitset& b) +{ + m_bits = b.m_bits; + m_num_bits = b.m_num_bits; + return *this; +} + +#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES + +template +inline dynamic_bitset:: +dynamic_bitset(dynamic_bitset&& b) + : m_bits(boost::move(b.m_bits)), m_num_bits(boost::move(b.m_num_bits)) +{ + // Required so that assert(m_check_invariants()); works. + assert((b.m_bits = buffer_type()).empty()); + b.m_num_bits = 0; +} + +template +inline dynamic_bitset& dynamic_bitset:: +operator=(dynamic_bitset&& b) +{ + if (boost::addressof(b) == this) { return *this; } + + m_bits = boost::move(b.m_bits); + m_num_bits = boost::move(b.m_num_bits); + // Required so that assert(m_check_invariants()); works. + assert((b.m_bits = buffer_type()).empty()); + b.m_num_bits = 0; + return *this; +} + +#endif // BOOST_NO_CXX11_RVALUE_REFERENCES + +template +inline typename dynamic_bitset::allocator_type +dynamic_bitset::get_allocator() const +{ + return m_bits.get_allocator(); +} + +//----------------------------------------------------------------------------- +// size changing operations + +template +void dynamic_bitset:: +resize(size_type num_bits, bool value) // strong guarantee +{ + + const size_type old_num_blocks = num_blocks(); + const size_type required_blocks = calc_num_blocks(num_bits); + + const block_type v = value? ~Block(0) : Block(0); + + if (required_blocks != old_num_blocks) { + m_bits.resize(required_blocks, v); // s.g. (copy) + } + + + // At this point: + // + // - if the buffer was shrunk, we have nothing more to do, + // except a call to m_zero_unused_bits() + // + // - if it was enlarged, all the (used) bits in the new blocks have + // the correct value, but we have not yet touched those bits, if + // any, that were 'unused bits' before enlarging: if value == true, + // they must be set. + + if (value && (num_bits > m_num_bits)) { + + const block_width_type extra_bits = count_extra_bits(); + if (extra_bits) { + assert(old_num_blocks >= 1 && old_num_blocks <= m_bits.size()); + + // Set them. + m_bits[old_num_blocks - 1] |= (v << extra_bits); + } + + } + + m_num_bits = num_bits; + m_zero_unused_bits(); + +} + +template +void dynamic_bitset:: +clear() // no throw +{ + m_bits.clear(); + m_num_bits = 0; +} + + +template +void dynamic_bitset:: +push_back(bool bit) +{ + const size_type sz = size(); + resize(sz + 1); + set(sz, bit); +} + +template +void dynamic_bitset:: +pop_back() +{ + const size_type old_num_blocks = num_blocks(); + const size_type required_blocks = calc_num_blocks(m_num_bits - 1); + + if (required_blocks != old_num_blocks) { + m_bits.pop_back(); + } + + --m_num_bits; + m_zero_unused_bits(); +} + + +template +void dynamic_bitset:: +append(Block value) // strong guarantee +{ + const block_width_type r = count_extra_bits(); + + if (r == 0) { + // the buffer is empty, or all blocks are filled + m_bits.push_back(value); + } + else { + m_bits.push_back(value >> (bits_per_block - r)); + m_bits[m_bits.size() - 2] |= (value << r); // m_bits.size() >= 2 + } + + m_num_bits += bits_per_block; + assert(m_check_invariants()); + +} + + +//----------------------------------------------------------------------------- +// bitset operations +template +dynamic_bitset& +dynamic_bitset::operator&=(const dynamic_bitset& rhs) +{ + assert(size() == rhs.size()); + for (size_type i = 0; i < num_blocks(); ++i) + m_bits[i] &= rhs.m_bits[i]; + return *this; +} + +template +dynamic_bitset& +dynamic_bitset::operator|=(const dynamic_bitset& rhs) +{ + assert(size() == rhs.size()); + for (size_type i = 0; i < num_blocks(); ++i) + m_bits[i] |= rhs.m_bits[i]; + //m_zero_unused_bits(); + return *this; +} + +template +dynamic_bitset& +dynamic_bitset::operator^=(const dynamic_bitset& rhs) +{ + assert(size() == rhs.size()); + for (size_type i = 0; i < this->num_blocks(); ++i) + m_bits[i] ^= rhs.m_bits[i]; + //m_zero_unused_bits(); + return *this; +} + +template +dynamic_bitset& +dynamic_bitset::operator-=(const dynamic_bitset& rhs) +{ + assert(size() == rhs.size()); + for (size_type i = 0; i < num_blocks(); ++i) + m_bits[i] &= ~rhs.m_bits[i]; + //m_zero_unused_bits(); + return *this; +} + +// +// NOTE: +// Note that the 'if (r != 0)' is crucial to avoid undefined +// behavior when the left hand operand of >> isn't promoted to a +// wider type (because rs would be too large). +// +template +dynamic_bitset& +dynamic_bitset::operator<<=(size_type n) +{ + if (n >= m_num_bits) + return reset(); + //else + if (n > 0) { + + size_type const last = num_blocks() - 1; // num_blocks() is >= 1 + size_type const div = n / bits_per_block; // div is <= last + block_width_type const r = bit_index(n); + block_type * const b = &m_bits[0]; + + if (r != 0) { + + block_width_type const rs = bits_per_block - r; + + for (size_type i = last-div; i>0; --i) { + b[i+div] = (b[i] << r) | (b[i-1] >> rs); + } + b[div] = b[0] << r; + + } + else { + for (size_type i = last-div; i>0; --i) { + b[i+div] = b[i]; + } + b[div] = b[0]; + } + + // zero out div blocks at the less significant end + std::fill_n(m_bits.begin(), div, static_cast(0)); + + // zero out any 1 bit that flowed into the unused part + m_zero_unused_bits(); // thanks to Lester Gong + + } + + return *this; + + +} + + +// +// NOTE: +// see the comments to operator <<= +// +template +dynamic_bitset & dynamic_bitset::operator>>=(size_type n) { + if (n >= m_num_bits) { + return reset(); + } + //else + if (n>0) { + + size_type const last = num_blocks() - 1; // num_blocks() is >= 1 + size_type const div = n / bits_per_block; // div is <= last + block_width_type const r = bit_index(n); + block_type * const b = &m_bits[0]; + + + if (r != 0) { + + block_width_type const ls = bits_per_block - r; + + for (size_type i = div; i < last; ++i) { + b[i-div] = (b[i] >> r) | (b[i+1] << ls); + } + // r bits go to zero + b[last-div] = b[last] >> r; + } + + else { + for (size_type i = div; i <= last; ++i) { + b[i-div] = b[i]; + } + // note the '<=': the last iteration 'absorbs' + // b[last-div] = b[last] >> 0; + } + + + + // div blocks are zero filled at the most significant end + std::fill_n(m_bits.begin() + (num_blocks()-div), div, static_cast(0)); + } + + return *this; +} + + +template +dynamic_bitset +dynamic_bitset::operator<<(size_type n) const +{ + dynamic_bitset r(*this); + return r <<= n; +} + +template +dynamic_bitset +dynamic_bitset::operator>>(size_type n) const +{ + dynamic_bitset r(*this); + return r >>= n; +} + + +//----------------------------------------------------------------------------- +// basic bit operations + +template +dynamic_bitset& +dynamic_bitset::set(size_type pos, + size_type len, bool val) +{ + if (val) + return range_operation(pos, len, set_block_partial, set_block_full); + else + return range_operation(pos, len, reset_block_partial, reset_block_full); +} + +template +dynamic_bitset& +dynamic_bitset::set(size_type pos, bool val) +{ + assert(pos < m_num_bits); + + if (val) + m_bits[block_index(pos)] |= bit_mask(pos); + else + reset(pos); + + return *this; +} + +template +dynamic_bitset& +dynamic_bitset::set() +{ + std::fill(m_bits.begin(), m_bits.end(), static_cast(~0)); + m_zero_unused_bits(); + return *this; +} + +template +inline dynamic_bitset& +dynamic_bitset::reset(size_type pos, size_type len) +{ + return range_operation(pos, len, reset_block_partial, reset_block_full); +} + +template +dynamic_bitset& +dynamic_bitset::reset(size_type pos) +{ + assert(pos < m_num_bits); +#if defined __MWERKS__ && BOOST_WORKAROUND(__MWERKS__, <= 0x3003) // 8.x + // CodeWarrior 8 generates incorrect code when the &=~ is compiled, + // use the |^ variation instead.. + m_bits[block_index(pos)] |= bit_mask(pos); + m_bits[block_index(pos)] ^= bit_mask(pos); +#else + m_bits[block_index(pos)] &= ~bit_mask(pos); +#endif + return *this; +} + +template +dynamic_bitset& +dynamic_bitset::reset() +{ + std::fill(m_bits.begin(), m_bits.end(), Block(0)); + return *this; +} + +template +dynamic_bitset& +dynamic_bitset::flip(size_type pos, size_type len) +{ + return range_operation(pos, len, flip_block_partial, flip_block_full); +} + +template +dynamic_bitset& +dynamic_bitset::flip(size_type pos) +{ + assert(pos < m_num_bits); + m_bits[block_index(pos)] ^= bit_mask(pos); + return *this; +} + +template +dynamic_bitset& +dynamic_bitset::flip() +{ + for (size_type i = 0; i < num_blocks(); ++i) + m_bits[i] = ~m_bits[i]; + m_zero_unused_bits(); + return *this; +} + +template +bool dynamic_bitset::m_unchecked_test(size_type pos) const +{ + return (m_bits[block_index(pos)] & bit_mask(pos)) != 0; +} + +template +bool dynamic_bitset::test(size_type pos) const +{ + assert(pos < m_num_bits); + return m_unchecked_test(pos); +} + +template +bool dynamic_bitset::test_set(size_type pos, bool val) +{ + bool const b = test(pos); + if (b != val) { + set(pos, val); + } + return b; +} + +template +bool dynamic_bitset::all() const +{ + if (empty()) { + return true; + } + + const block_width_type extra_bits = count_extra_bits(); + block_type const all_ones = static_cast(~0); + + if (extra_bits == 0) { + for (size_type i = 0, e = num_blocks(); i < e; ++i) { + if (m_bits[i] != all_ones) { + return false; + } + } + } else { + for (size_type i = 0, e = num_blocks() - 1; i < e; ++i) { + if (m_bits[i] != all_ones) { + return false; + } + } + const block_type mask = (block_type(1) << extra_bits) - 1; + if (m_highest_block() != mask) { + return false; + } + } + return true; +} + +template +bool dynamic_bitset::any() const +{ + for (size_type i = 0; i < num_blocks(); ++i) + if (m_bits[i]) + return true; + return false; +} + +template +inline bool dynamic_bitset::none() const +{ + return !any(); +} + +template +dynamic_bitset +dynamic_bitset::operator~() const +{ + dynamic_bitset b(*this); + b.flip(); + return b; +} + +template +typename dynamic_bitset::size_type +dynamic_bitset::count() const BOOST_NOEXCEPT +{ + using detail::dynamic_bitset_impl::table_width; + using detail::dynamic_bitset_impl::access_by_bytes; + using detail::dynamic_bitset_impl::access_by_blocks; + using detail::dynamic_bitset_impl::value_to_type; + +#if BOOST_WORKAROUND(__GNUC__, == 4) && (__GNUC_MINOR__ == 3) && (__GNUC_PATCHLEVEL__ == 3) + // NOTE: Explicit qualification of "bits_per_block" + // breaks compilation on gcc 4.3.3 + enum { no_padding = bits_per_block == CHAR_BIT * sizeof(Block) }; +#else + // NOTE: Explicitly qualifying "bits_per_block" to workaround + // regressions of gcc 3.4.x + enum { no_padding = + dynamic_bitset::bits_per_block + == CHAR_BIT * sizeof(Block) }; +#endif + + enum { enough_table_width = table_width >= CHAR_BIT }; + +#if ((defined(BOOST_MSVC) && (BOOST_MSVC >= 1600)) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64)) + // Windows popcount is effective starting from the unsigned short type + enum { uneffective_popcount = sizeof(Block) < sizeof(unsigned short) }; +#elif defined(BOOST_GCC) || defined(__clang__) || (defined(BOOST_INTEL) && defined(__GNUC__)) + // GCC popcount is effective starting from the unsigned int type + enum { uneffective_popcount = sizeof(Block) < sizeof(unsigned int) }; +#else + enum { uneffective_popcount = true }; +#endif + + enum { mode = (no_padding && enough_table_width && uneffective_popcount) + ? access_by_bytes + : access_by_blocks }; + + return do_count(m_bits.begin(), num_blocks(), Block(0), + static_cast *>(0)); +} + + +//----------------------------------------------------------------------------- +// conversions + + +template +void to_string_helper(const dynamic_bitset & b, stringT & s, + bool dump_all) +{ + typedef typename stringT::traits_type Tr; + typedef typename stringT::value_type Ch; + + BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, std::locale()); + const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0'); + const Ch one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1'); + + // Note that this function may access (when + // dump_all == true) bits beyond position size() - 1 + + typedef typename dynamic_bitset::size_type size_type; + + const size_type len = dump_all? + dynamic_bitset::bits_per_block * b.num_blocks(): + b.size(); + s.assign (len, zero); + + for (size_type i = 0; i < len; ++i) { + if (b.m_unchecked_test(i)) + Tr::assign(s[len - 1 - i], one); + + } + +} + + +// A comment similar to the one about the constructor from +// basic_string can be done here. Thanks to James Kanze for +// making me (Gennaro) realize this important separation of +// concerns issue, as well as many things about i18n. +// +template +inline void +to_string(const dynamic_bitset& b, stringT& s) +{ + to_string_helper(b, s, false); +} + + +// Differently from to_string this function dumps out +// every bit of the internal representation (may be +// useful for debugging purposes) +// +template +inline void +dump_to_string(const dynamic_bitset& b, stringT& s) +{ + to_string_helper(b, s, true /* =dump_all*/); +} + +template +inline void +to_block_range(const dynamic_bitset& b, + BlockOutputIterator result) +{ + // note how this copies *all* bits, including the + // unused ones in the last block (which are zero) + std::copy(b.m_bits.begin(), b.m_bits.end(), result); +} + +template +unsigned long dynamic_bitset:: +to_ulong() const +{ + + if (m_num_bits == 0) + return 0; // convention + + // Check for overflows. This may be a performance burden on very + // large bitsets but is required by the specification, sorry + if (find_next(ulong_width - 1) != npos) + BOOST_THROW_EXCEPTION(std::overflow_error("boost::dynamic_bitset::to_ulong overflow")); + + + // Ok, from now on we can be sure there's no "on" bit + // beyond the "allowed" positions + typedef unsigned long result_type; + + const size_type maximum_size = + (std::min)(m_num_bits, static_cast(ulong_width)); + + const size_type last_block = block_index( maximum_size - 1 ); + + assert((last_block * bits_per_block) < static_cast(ulong_width)); + + result_type result = 0; + for (size_type i = 0; i <= last_block; ++i) { + const size_type offset = i * bits_per_block; + result |= (static_cast(m_bits[i]) << offset); + } + + return result; +} + +template +inline typename dynamic_bitset::size_type +dynamic_bitset::size() const BOOST_NOEXCEPT +{ + return m_num_bits; +} + +template +inline typename dynamic_bitset::size_type +dynamic_bitset::num_blocks() const BOOST_NOEXCEPT +{ + return m_bits.size(); +} + +template +inline typename dynamic_bitset::size_type +dynamic_bitset::max_size() const BOOST_NOEXCEPT +{ + // Semantics of vector<>::max_size() aren't very clear + // (see lib issue 197) and many library implementations + // simply return dummy values, _unrelated_ to the underlying + // allocator. + // + // Given these problems, I was tempted to not provide this + // function at all but the user could need it if he provides + // his own allocator. + // + + const size_type m = detail::dynamic_bitset_impl:: + vector_max_size_workaround(m_bits); + + return m <= (size_type(-1)/bits_per_block) ? + m * bits_per_block : + size_type(-1); +} + +template +inline bool dynamic_bitset::empty() const BOOST_NOEXCEPT +{ + return size() == 0; +} + +template +inline typename dynamic_bitset::size_type +dynamic_bitset::capacity() const BOOST_NOEXCEPT +{ + return m_bits.capacity() * bits_per_block; +} + +template +inline void dynamic_bitset::reserve(size_type num_bits) +{ + m_bits.reserve(calc_num_blocks(num_bits)); +} + +template +void dynamic_bitset::shrink_to_fit() +{ + if (m_bits.size() < m_bits.capacity()) { + buffer_type(m_bits).swap(m_bits); + } +} + +template +bool dynamic_bitset:: +is_subset_of(const dynamic_bitset& a) const +{ + assert(size() == a.size()); + for (size_type i = 0; i < num_blocks(); ++i) + if (m_bits[i] & ~a.m_bits[i]) + return false; + return true; +} + +template +bool dynamic_bitset:: +is_proper_subset_of(const dynamic_bitset& a) const +{ + assert(size() == a.size()); + assert(num_blocks() == a.num_blocks()); + + bool proper = false; + for (size_type i = 0; i < num_blocks(); ++i) { + const Block & bt = m_bits[i]; + const Block & ba = a.m_bits[i]; + + if (bt & ~ba) + return false; // not a subset at all + if (ba & ~bt) + proper = true; + } + return proper; +} + +template +bool dynamic_bitset::intersects(const dynamic_bitset & b) const +{ + size_type common_blocks = num_blocks() < b.num_blocks() + ? num_blocks() : b.num_blocks(); + + for(size_type i = 0; i < common_blocks; ++i) { + if(m_bits[i] & b.m_bits[i]) + return true; + } + return false; +} + +// -------------------------------- +// lookup + +// look for the first bit "on", starting +// from the block with index first_block +// +template +typename dynamic_bitset::size_type +dynamic_bitset::m_do_find_from(size_type first_block) const +{ + size_type i = first_block; + + // skip null blocks + while (i < num_blocks() && m_bits[i] == 0) + ++i; + + if (i >= num_blocks()) + return npos; // not found + + return i * bits_per_block + static_cast(detail::lowest_bit(m_bits[i])); +} + + +template +typename dynamic_bitset::size_type +dynamic_bitset::find_first() const +{ + return m_do_find_from(0); +} + + +template +typename dynamic_bitset::size_type +dynamic_bitset::find_next(size_type pos) const +{ + + const size_type sz = size(); + if (pos >= (sz-1) || sz == 0) + return npos; + + ++pos; + + const size_type blk = block_index(pos); + const block_width_type ind = bit_index(pos); + + // shift bits upto one immediately after current + const Block fore = m_bits[blk] >> ind; + + return fore? + pos + static_cast(detail::lowest_bit(fore)) + : + m_do_find_from(blk + 1); + +} + + + +//----------------------------------------------------------------------------- +// comparison + +template +bool operator==(const dynamic_bitset& a, + const dynamic_bitset& b) +{ + return (a.m_num_bits == b.m_num_bits) + && (a.m_bits == b.m_bits); +} + +template +inline bool operator!=(const dynamic_bitset& a, + const dynamic_bitset& b) +{ + return !(a == b); +} + +template +bool operator<(const dynamic_bitset& a, + const dynamic_bitset& b) +{ +// assert(a.size() == b.size()); + + typedef BOOST_DEDUCED_TYPENAME dynamic_bitset::size_type size_type; + + size_type asize(a.size()); + size_type bsize(b.size()); + + if (!bsize) + { + return false; + } + else if (!asize) + { + return true; + } + else if (asize == bsize) + { + for (size_type ii = a.num_blocks(); ii > 0; --ii) + { + size_type i = ii-1; + if (a.m_bits[i] < b.m_bits[i]) + return true; + else if (a.m_bits[i] > b.m_bits[i]) + return false; + } + return false; + } + else + { + + size_type leqsize(std::min BOOST_PREVENT_MACRO_SUBSTITUTION(asize,bsize)); + + for (size_type ii = 0; ii < leqsize; ++ii,--asize,--bsize) + { + size_type i = asize-1; + size_type j = bsize-1; + if (a[i] < b[j]) + return true; + else if (a[i] > b[j]) + return false; + } + return (a.size() < b.size()); + } +} + +template +bool oplessthan(const dynamic_bitset& a, + const dynamic_bitset& b) +{ +// assert(a.size() == b.size()); + + typedef BOOST_DEDUCED_TYPENAME dynamic_bitset::size_type size_type; + + size_type asize(a.num_blocks()); + size_type bsize(b.num_blocks()); + assert(asize == 3); + assert(bsize == 4); + + if (!bsize) + { + return false; + } + else if (!asize) + { + return true; + } + else + { + + size_type leqsize(std::min BOOST_PREVENT_MACRO_SUBSTITUTION(asize,bsize)); + assert(leqsize == 3); + + //if (a.size() == 0) + // return false; + + // Since we are storing the most significant bit + // at pos == size() - 1, we need to do the comparisons in reverse. + // + for (size_type ii = 0; ii < leqsize; ++ii,--asize,--bsize) + { + size_type i = asize-1; + size_type j = bsize-1; + if (a.m_bits[i] < b.m_bits[j]) + return true; + else if (a.m_bits[i] > b.m_bits[j]) + return false; + } + return (a.num_blocks() < b.num_blocks()); + } +} + +template +inline bool operator<=(const dynamic_bitset& a, + const dynamic_bitset& b) +{ + return !(a > b); +} + +template +inline bool operator>(const dynamic_bitset& a, + const dynamic_bitset& b) +{ + return b < a; +} + +template +inline bool operator>=(const dynamic_bitset& a, + const dynamic_bitset& b) +{ + return !(a < b); +} + +//----------------------------------------------------------------------------- +// hash operations + +template +inline std::size_t hash_value(const dynamic_bitset& a) +{ + std::size_t res = hash_value(a.m_num_bits); + boost::hash_combine(res, a.m_bits); + return res; +} + +//----------------------------------------------------------------------------- +// stream operations + +#ifdef BOOST_OLD_IOSTREAMS +template < typename Block, typename Alloc> +std::ostream& +operator<<(std::ostream& os, const dynamic_bitset& b) +{ + // NOTE: since this is aimed at "classic" iostreams, exception + // masks on the stream are not supported. The library that + // ships with gcc 2.95 has an exceptions() member function but + // nothing is actually implemented; not even the class ios::failure. + + using namespace std; + + const ios::iostate ok = ios::goodbit; + ios::iostate err = ok; + + if (os.opfx()) { + + //try + typedef typename dynamic_bitset::size_type bitsetsize_type; + + const bitsetsize_type sz = b.size(); + std::streambuf * buf = os.rdbuf(); + size_t npad = os.width() <= 0 // careful: os.width() is signed (and can be < 0) + || (bitsetsize_type) os.width() <= sz? 0 : os.width() - sz; + + const char fill_char = os.fill(); + const ios::fmtflags adjustfield = os.flags() & ios::adjustfield; + + // if needed fill at left; pad is decresed along the way + if (adjustfield != ios::left) { + for (; 0 < npad; --npad) + if (fill_char != buf->sputc(fill_char)) { + err |= ios::failbit; + break; + } + } + + if (err == ok) { + // output the bitset + for (bitsetsize_type i = b.size(); 0 < i; --i) { + const char dig = b.test(i-1)? '1' : '0'; + if (EOF == buf->sputc(dig)) { + err |= ios::failbit; + break; + } + } + } + + if (err == ok) { + // if needed fill at right + for (; 0 < npad; --npad) { + if (fill_char != buf->sputc(fill_char)) { + err |= ios::failbit; + break; + } + } + } + + os.osfx(); + os.width(0); + + } // if opfx + + if(err != ok) + os.setstate(err); // assume this does NOT throw + return os; + +} +#else + +template +std::basic_ostream& +operator<<(std::basic_ostream& os, + const dynamic_bitset& b) +{ + + using namespace std; + + const ios_base::iostate ok = ios_base::goodbit; + ios_base::iostate err = ok; + + typename basic_ostream::sentry cerberos(os); + if (cerberos) { + + BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, os.getloc()); + const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0'); + const Ch one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1'); + + BOOST_TRY { + + typedef typename dynamic_bitset::size_type bitset_size_type; + typedef basic_streambuf buffer_type; + + buffer_type * buf = os.rdbuf(); + // careful: os.width() is signed (and can be < 0) + const bitset_size_type width = (os.width() <= 0) ? 0 : static_cast(os.width()); + streamsize npad = (width <= b.size()) ? 0 : width - b.size(); + + const Ch fill_char = os.fill(); + const ios_base::fmtflags adjustfield = os.flags() & ios_base::adjustfield; + + // if needed fill at left; pad is decreased along the way + if (adjustfield != ios_base::left) { + for (; 0 < npad; --npad) + if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) { + err |= ios_base::failbit; + break; + } + } + + if (err == ok) { + // output the bitset + for (bitset_size_type i = b.size(); 0 < i; --i) { + typename buffer_type::int_type + ret = buf->sputc(b.test(i-1)? one : zero); + if (Tr::eq_int_type(Tr::eof(), ret)) { + err |= ios_base::failbit; + break; + } + } + } + + if (err == ok) { + // if needed fill at right + for (; 0 < npad; --npad) { + if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) { + err |= ios_base::failbit; + break; + } + } + } + + + os.width(0); + + } BOOST_CATCH (...) { // see std 27.6.1.1/4 + bool rethrow = false; + BOOST_TRY { os.setstate(ios_base::failbit); } BOOST_CATCH (...) { rethrow = true; } BOOST_CATCH_END + + if (rethrow) + BOOST_RETHROW; + } + BOOST_CATCH_END + } + + if(err != ok) + os.setstate(err); // may throw exception + return os; + +} +#endif + + +#ifdef BOOST_OLD_IOSTREAMS + + // A sentry-like class that calls isfx in its destructor. + // "Necessary" because bit_appender::do_append may throw. + class pseudo_sentry { + std::istream & m_r; + const bool m_ok; + public: + explicit pseudo_sentry(std::istream & r) : m_r(r), m_ok(r.ipfx(0)) { } + ~pseudo_sentry() { m_r.isfx(); } + operator bool() const { return m_ok; } + }; + +template +std::istream& +operator>>(std::istream& is, dynamic_bitset& b) +{ + +// Extractor for classic IO streams (libstdc++ < 3.0) +// ----------------------------------------------------// +// It's assumed that the stream buffer functions, and +// the stream's setstate() _cannot_ throw. + + + typedef dynamic_bitset bitset_type; + typedef typename bitset_type::size_type size_type; + + std::ios::iostate err = std::ios::goodbit; + pseudo_sentry cerberos(is); // skips whitespaces + if(cerberos) { + + b.clear(); + + const std::streamsize w = is.width(); + const size_type limit = w > 0 && static_cast(w) < b.max_size() + ? static_cast(w) : b.max_size(); + typename bitset_type::bit_appender appender(b); + std::streambuf * buf = is.rdbuf(); + for(int c = buf->sgetc(); appender.get_count() < limit; c = buf->snextc() ) { + + if (c == EOF) { + err |= std::ios::eofbit; + break; + } + else if (char(c) != '0' && char(c) != '1') + break; // non digit character + + else { + BOOST_TRY { + appender.do_append(char(c) == '1'); + } + BOOST_CATCH(...) { + is.setstate(std::ios::failbit); // assume this can't throw + BOOST_RETHROW; + } + BOOST_CATCH_END + } + + } // for + } + + is.width(0); + if (b.size() == 0) + err |= std::ios::failbit; + if (err != std::ios::goodbit) + is.setstate (err); // may throw + + return is; +} + +#else // BOOST_OLD_IOSTREAMS + +template +std::basic_istream& +operator>>(std::basic_istream& is, dynamic_bitset& b) +{ + + using namespace std; + + typedef dynamic_bitset bitset_type; + typedef typename bitset_type::size_type size_type; + + const streamsize w = is.width(); + const size_type limit = 0 < w && static_cast(w) < b.max_size()? + static_cast(w) : b.max_size(); + + ios_base::iostate err = ios_base::goodbit; + typename basic_istream::sentry cerberos(is); // skips whitespaces + if(cerberos) { + + // in accordance with prop. resol. of lib DR 303 [last checked 4 Feb 2004] + BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, is.getloc()); + const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0'); + const Ch one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1'); + + b.clear(); + BOOST_TRY { + typename bitset_type::bit_appender appender(b); + basic_streambuf * buf = is.rdbuf(); + typename Tr::int_type c = buf->sgetc(); + for( ; appender.get_count() < limit; c = buf->snextc() ) { + + if (Tr::eq_int_type(Tr::eof(), c)) { + err |= ios_base::eofbit; + break; + } + else { + const Ch to_c = Tr::to_char_type(c); + const bool is_one = Tr::eq(to_c, one); + + if (!is_one && !Tr::eq(to_c, zero)) + break; // non digit character + + appender.do_append(is_one); + + } + + } // for + } + BOOST_CATCH (...) { + // catches from stream buf, or from vector: + // + // bits_stored bits have been extracted and stored, and + // either no further character is extractable or we can't + // append to the underlying vector (out of memory) + + bool rethrow = false; // see std 27.6.1.1/4 + BOOST_TRY { is.setstate(ios_base::badbit); } + BOOST_CATCH(...) { rethrow = true; } + BOOST_CATCH_END + + if (rethrow) + BOOST_RETHROW; + + } + BOOST_CATCH_END + } + + is.width(0); + if (b.size() == 0 /*|| !cerberos*/) + err |= ios_base::failbit; + if (err != ios_base::goodbit) + is.setstate (err); // may throw + + return is; + +} + + +#endif + + +//----------------------------------------------------------------------------- +// bitset operations + +template +dynamic_bitset +operator&(const dynamic_bitset& x, + const dynamic_bitset& y) +{ + dynamic_bitset b(x); + return b &= y; +} + +template +dynamic_bitset +operator|(const dynamic_bitset& x, + const dynamic_bitset& y) +{ + dynamic_bitset b(x); + return b |= y; +} + +template +dynamic_bitset +operator^(const dynamic_bitset& x, + const dynamic_bitset& y) +{ + dynamic_bitset b(x); + return b ^= y; +} + +template +dynamic_bitset +operator-(const dynamic_bitset& x, + const dynamic_bitset& y) +{ + dynamic_bitset b(x); + return b -= y; +} + +//----------------------------------------------------------------------------- +// namespace scope swap + +template +inline void +swap(dynamic_bitset& left, + dynamic_bitset& right) // no throw +{ + left.swap(right); +} + + +//----------------------------------------------------------------------------- +// private (on conforming compilers) member functions + + +template +inline typename dynamic_bitset::size_type +dynamic_bitset::calc_num_blocks(size_type num_bits) +{ + return num_bits / bits_per_block + + static_cast( num_bits % bits_per_block != 0 ); +} + +// gives a reference to the highest block +// +template +inline Block& dynamic_bitset::m_highest_block() +{ + return const_cast + (static_cast(this)->m_highest_block()); +} + +// gives a const-reference to the highest block +// +template +inline const Block& dynamic_bitset::m_highest_block() const +{ + assert(size() > 0 && num_blocks() > 0); + return m_bits.back(); +} + +template +dynamic_bitset& dynamic_bitset::range_operation( + size_type pos, size_type len, + Block (*partial_block_operation)(Block, size_type, size_type), + Block (*full_block_operation)(Block)) +{ + assert(pos + len <= m_num_bits); + + // Do nothing in case of zero length + if (!len) + return *this; + + // Use an additional asserts in order to detect size_type overflow + // For example: pos = 10, len = size_type_limit - 2, pos + len = 7 + // In case of overflow, 'pos + len' is always smaller than 'len' + assert(pos + len >= len); + + // Start and end blocks of the [pos; pos + len - 1] sequence + const size_type first_block = block_index(pos); + const size_type last_block = block_index(pos + len - 1); + + const size_type first_bit_index = bit_index(pos); + const size_type last_bit_index = bit_index(pos + len - 1); + + if (first_block == last_block) { + // Filling only a sub-block of a block + m_bits[first_block] = partial_block_operation(m_bits[first_block], + first_bit_index, last_bit_index); + } else { + // Check if the corner blocks won't be fully filled with 'val' + const size_type first_block_shift = bit_index(pos) ? 1 : 0; + const size_type last_block_shift = (bit_index(pos + len - 1) + == bits_per_block - 1) ? 0 : 1; + + // Blocks that will be filled with ~0 or 0 at once + const size_type first_full_block = first_block + first_block_shift; + const size_type last_full_block = last_block - last_block_shift; + + for (size_type i = first_full_block; i <= last_full_block; ++i) { + m_bits[i] = full_block_operation(m_bits[i]); + } + + // Fill the first block from the 'first' bit index to the end + if (first_block_shift) { + m_bits[first_block] = partial_block_operation(m_bits[first_block], + first_bit_index, bits_per_block - 1); + } + + // Fill the last block from the start to the 'last' bit index + if (last_block_shift) { + m_bits[last_block] = partial_block_operation(m_bits[last_block], + 0, last_bit_index); + } + } + + return *this; +} + +// If size() is not a multiple of bits_per_block +// then not all the bits in the last block are used. +// This function resets the unused bits (convenient +// for the implementation of many member functions) +// +template +inline void dynamic_bitset::m_zero_unused_bits() +{ + assert (num_blocks() == calc_num_blocks(m_num_bits)); + + // if != 0 this is the number of bits used in the last block + const block_width_type extra_bits = count_extra_bits(); + + if (extra_bits != 0) + m_highest_block() &= (Block(1) << extra_bits) - 1; +} + +// check class invariants +template +bool dynamic_bitset::m_check_invariants() const +{ + const block_width_type extra_bits = count_extra_bits(); + if (extra_bits > 0) { + const block_type mask = block_type(~0) << extra_bits; + if ((m_highest_block() & mask) != 0) + return false; + } + if (m_bits.size() > m_bits.capacity() || num_blocks() != calc_num_blocks(size())) + return false; + + return true; + +} + + +} // namespace boost + +#undef BOOST_BITSET_CHAR + +// std::hash support +#if !defined(BOOST_NO_CXX11_HDR_FUNCTIONAL) && !defined(BOOST_DYNAMIC_BITSET_NO_STD_HASH) +#include +namespace std +{ + template + struct hash< boost::dynamic_bitset > + { + typedef boost::dynamic_bitset argument_type; + typedef std::size_t result_type; + result_type operator()(const argument_type& a) const BOOST_NOEXCEPT + { + boost::hash hasher; + return hasher(a); + } + }; +} +#endif + +#endif // include guard + Index: libraries/win32/boost/include/boost/dynamic_bitset/serialization.hpp =================================================================== --- /dev/null +++ libraries/win32/boost/include/boost/dynamic_bitset/serialization.hpp @@ -0,0 +1,46 @@ +// ----------------------------------------------------------- +// +// Copyright (c) 2015 Seth Heeren +// +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +// +// ----------------------------------------------------------- + +#ifndef BOOST_DYNAMIC_BITSET_SERIALIZATION_HPP +#define BOOST_DYNAMIC_BITSET_SERIALIZATION_HPP + +#include "boost/dynamic_bitset/dynamic_bitset.hpp" +#include + +namespace boost { + + // implementation for optional zero-copy serialization support + template + class dynamic_bitset::serialize_impl + { + public: + template + static void serialize(Ar& ar, dynamic_bitset& bs, unsigned) { + ar & serialization::make_nvp("m_num_bits", bs.m_num_bits) + & serialization::make_nvp("m_bits", bs.m_bits); + } + }; + +} + +// ADL hook to Boost Serialization library +namespace boost { + namespace serialization { + + template + void serialize(Ar& ar, dynamic_bitset& bs, unsigned version) { + dynamic_bitset::serialize_impl::serialize(ar, bs, version); + } + + } // namespace serialization +} // namespace boost + +#endif // include guard + Index: libraries/win32/boost/include/boost/dynamic_bitset_fwd.hpp =================================================================== --- /dev/null +++ libraries/win32/boost/include/boost/dynamic_bitset_fwd.hpp @@ -0,0 +1,25 @@ +// ----------------------------------------------------------- +// +// Copyright (c) 2001-2002 Chuck Allison and Jeremy Siek +// Copyright (c) 2003-2004 Gennaro Prota +// +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +// +// ----------------------------------------------------------- + +#ifndef BOOST_DYNAMIC_BITSET_FWD_HPP +#define BOOST_DYNAMIC_BITSET_FWD_HPP + +#include + +namespace boost { + +template > +class dynamic_bitset; + +} + +#endif // include guard Index: source/ps/Game.cpp =================================================================== --- source/ps/Game.cpp +++ source/ps/Game.cpp @@ -217,11 +217,14 @@ std::string mapType; scriptInterface.GetProperty(attribs, "mapType", mapType); - + float speed; if (scriptInterface.HasProperty(attribs, "gameSpeed") && scriptInterface.GetProperty(attribs, "gameSpeed", speed)) SetSimRate(speed); + bool experimentalLos; + scriptInterface.GetProperty(attribs, "ExperimentalLos", experimentalLos); + LDR_BeginRegistering(); RegMemFun(m_Simulation2, &CSimulation2::ProgressiveLoad, L"Simulation init", 1000); @@ -264,6 +267,10 @@ RegMemFun(this, &CGame::LoadVisualReplayData, L"Loading visual replay data", 1000); LDR_EndRegistering(); + + CmpPtr cmpRangeManager(*m_Simulation2, SYSTEM_ENTITY); + if (cmpRangeManager) + cmpRangeManager->SetVisionBlockingEnabled(experimentalLos); } int CGame::LoadInitialState() Index: source/simulation2/components/CCmpFootprint.cpp =================================================================== --- source/simulation2/components/CCmpFootprint.cpp +++ source/simulation2/components/CCmpFootprint.cpp @@ -1,4 +1,4 @@ -/* Copyright (C) 2018 Wildfire Games. +/* Copyright (C) 2019 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. is free software: you can redistribute it and/or modify @@ -135,6 +135,11 @@ Init(paramNode); } + virtual entity_pos_t GetHeight() const + { + return m_Height; + } + virtual void GetShape(EShape& shape, entity_pos_t& size0, entity_pos_t& size1, entity_pos_t& height) const { shape = m_Shape; Index: source/simulation2/components/CCmpRangeManager.cpp =================================================================== --- source/simulation2/components/CCmpRangeManager.cpp +++ source/simulation2/components/CCmpRangeManager.cpp @@ -17,6 +17,8 @@ #include "precompiled.h" +#include + #include "simulation2/system/Component.h" #include "ICmpRangeManager.h" @@ -24,6 +26,7 @@ #include "simulation2/system/EntityMap.h" #include "simulation2/MessageTypes.h" #include "simulation2/components/ICmpFogging.h" +#include "simulation2/components/ICmpFootprint.h" #include "simulation2/components/ICmpMirage.h" #include "simulation2/components/ICmpOwnership.h" #include "simulation2/components/ICmpPosition.h" @@ -44,7 +47,9 @@ #include "renderer/Scene.h" #define LOS_TILES_RATIO 8 -#define DEBUG_RANGE_MANAGER_BOUNDS 0 +// Enables runtime tests for vision blocking computation. +// Program will trigger exception when finds problem. +#define DEBUG_VIS_COMP 0 /** * Representation of a range query. @@ -214,10 +219,11 @@ { EntityData() : visibilities(0), size(0), visionSharing(0), - owner(-1), flags(FlagMasks::Normal) + owner(-1), flags(FlagMasks::Normal), height(0) { } entity_pos_t x, z; entity_pos_t visionRange; + u16 height; u32 visibilities; // 2-bit visibility, per player u32 size; u16 visionSharing; // 1-bit per player @@ -233,7 +239,7 @@ inline void SetFlag(u8 mask, bool val) { flags = val ? (flags | mask) : (flags & ~mask); } }; -cassert(sizeof(EntityData) == 24); +cassert(sizeof(EntityData) == 28); /** * Serialization helper template for Query @@ -290,6 +296,7 @@ serialize.NumberU16_Unbounded("vision sharing", value.visionSharing); serialize.NumberI8_Unbounded("owner", value.owner); serialize.NumberU8_Unbounded("flags", value.flags); + serialize.NumberU16_Unbounded("height", value.height); } }; @@ -327,7 +334,7 @@ * queries. * * LOS implementation is based on the model described in GPG2. - * (TODO: would be nice to make it cleverer, so e.g. mountains and walls + * (TODO: would be nice to make it cleverer, so e.g. walls * can block vision) */ class CCmpRangeManager : public ICmpRangeManager @@ -394,6 +401,29 @@ // Lazily constructed when it's needed, to save memory in smaller games. std::vector > m_LosPlayerCounts; + // Large amount of calls so cache it + CTerrain* m_Terrain; + + // Map used by all players and vertexes with the same structure as m_LosState. + // Used in los update to determine if given tile was visible. + // No need to serialise. + boost::dynamic_bitset<> m_Vismap; + + // Map used by all players and vertexes with the same structure as m_LosState. + // Used in los update to determine if given tile blocked vision. + // No need to serialise. + boost::dynamic_bitset<> m_IsBlockingVision; + + // Used in los update to know if in current computation was vision blocked. + bool m_VisionBlocked; + + bool m_VisionBlockingEnabled; + +#if DEBUG_VIS_COMP + // Holds if tile was checked by los update. + boost::dynamic_bitset<> m_VisComputedBefore; +#endif + // 2-bit ELosState per player, starting with player 1 (not 0!) up to player MAX_LOS_PLAYER_ID (inclusive) std::vector m_LosState; @@ -443,6 +473,10 @@ m_LosCircular = false; m_TerrainVerticesPerSide = 0; + + m_VisionBlockingEnabled = false; + + m_Terrain = nullptr; } virtual void Deinit() @@ -452,6 +486,8 @@ template void SerializeCommon(S& serialize) { + serialize.Bool("vision blocking enabled", m_VisionBlockingEnabled); + debug_printf("serialisation -> vision blocking set to %d\n", m_VisionBlockingEnabled); serialize.NumberFixed_Unbounded("world x0", m_WorldX0); serialize.NumberFixed_Unbounded("world z0", m_WorldZ0); serialize.NumberFixed_Unbounded("world x1", m_WorldX1); @@ -539,6 +575,11 @@ if (cmpObstruction) entdata.size = cmpObstruction->GetSize().ToInt_RoundToInfinity(); + // Store height + CmpPtr cmpFootprint(GetSimContext(), ent); + if (cmpFootprint) + entdata.height = cmpFootprint->GetHeight().ToInt_RoundToNearest(); + // Remember this entity m_EntityData.insert(ent, entdata); break; @@ -562,9 +603,9 @@ CFixedVector2D to(msgData.x, msgData.z); m_Subdivision.Move(ent, from, to, it->second.size); if (it->second.HasFlag()) - SharingLosMove(it->second.visionSharing, it->second.visionRange, from, to); + SharingLosMove(it->second.visionSharing, it->second.visionRange, from, to, it->second.height); else - LosMove(it->second.owner, it->second.visionRange, from, to); + LosMove(it->second.owner, it->second.visionRange, from, to, it->second.height); i32 oldLosTile = PosToLosTilesHelper(it->second.x, it->second.z); i32 newLosTile = PosToLosTilesHelper(msgData.x, msgData.z); if (oldLosTile != newLosTile) @@ -578,9 +619,9 @@ CFixedVector2D to(msgData.x, msgData.z); m_Subdivision.Add(ent, to, it->second.size); if (it->second.HasFlag()) - SharingLosAdd(it->second.visionSharing, it->second.visionRange, to); + SharingLosAdd(it->second.visionSharing, it->second.visionRange, to, it->second.height); else - LosAdd(it->second.owner, it->second.visionRange, to); + LosAdd(it->second.owner, it->second.visionRange, to, it->second.height); AddToTile(PosToLosTilesHelper(msgData.x, msgData.z), ent); } @@ -595,9 +636,9 @@ CFixedVector2D from(it->second.x, it->second.z); m_Subdivision.Remove(ent, from, it->second.size); if (it->second.HasFlag()) - SharingLosRemove(it->second.visionSharing, it->second.visionRange, from); + SharingLosRemove(it->second.visionSharing, it->second.visionRange, from, it->second.height); else - LosRemove(it->second.owner, it->second.visionRange, from); + LosRemove(it->second.owner, it->second.visionRange, from, it->second.height); RemoveFromTile(PosToLosTilesHelper(it->second.x, it->second.z), ent); } @@ -628,14 +669,14 @@ if (!it->second.HasFlag()) { CFixedVector2D pos(it->second.x, it->second.z); - LosRemove(it->second.owner, it->second.visionRange, pos); - LosAdd(msgData.to, it->second.visionRange, pos); + LosRemove(it->second.owner, it->second.visionRange, pos, it->second.height); + LosAdd(msgData.to, it->second.visionRange, pos, it->second.height); } if (it->second.HasFlag()) { - RevealShore(it->second.owner, false); - RevealShore(msgData.to, true); + RevealShore(it->second.owner, false, it->second.height); + RevealShore(msgData.to, true, it->second.height); } } @@ -697,13 +738,13 @@ CFixedVector2D pos(it->second.x, it->second.z); if (it->second.HasFlag()) { - SharingLosRemove(it->second.visionSharing, oldRange, pos); - SharingLosAdd(it->second.visionSharing, newRange, pos); + SharingLosRemove(it->second.visionSharing, oldRange, pos, it->second.height); + SharingLosAdd(it->second.visionSharing, newRange, pos, it->second.height); } else { - LosRemove(it->second.owner, oldRange, pos); - LosAdd(it->second.owner, newRange, pos); + LosRemove(it->second.owner, oldRange, pos, it->second.height); + LosAdd(it->second.owner, newRange, pos, it->second.height); } } @@ -737,9 +778,9 @@ entity_pos_t range = it->second.visionRange; CFixedVector2D pos(it->second.x, it->second.z); if (msgData.add) - LosAdd(msgData.player, range, pos); + LosAdd(msgData.player, range, pos, it->second.height); else - LosRemove(msgData.player, range, pos); + LosRemove(msgData.player, range, pos, it->second.height); } if (msgData.add) @@ -772,6 +813,10 @@ m_WorldZ1 = z1; m_TerrainVerticesPerSide = (i32)vertices; + CmpPtr cmpTerrain(GetSimContext(), SYSTEM_ENTITY); + if (cmpTerrain) + m_Terrain = cmpTerrain->GetCTerrain(); + ResetDerivedData(); } @@ -836,6 +881,13 @@ m_LosPlayerCounts.resize(MAX_LOS_PLAYER_ID+1); m_ExploredVertices.clear(); m_ExploredVertices.resize(MAX_LOS_PLAYER_ID+1, 0); + + // Just clear them so they are resized before computations + m_Vismap.clear(); + ENSURE(m_Vismap.empty()); + m_IsBlockingVision.clear(); + ENSURE(m_IsBlockingVision.empty()); + if (m_Deserializing) { // recalc current exploration stats. @@ -867,13 +919,13 @@ if (it->second.HasFlag()) { if (it->second.HasFlag()) - SharingLosAdd(it->second.visionSharing, it->second.visionRange, CFixedVector2D(it->second.x, it->second.z)); + SharingLosAdd(it->second.visionSharing, it->second.visionRange, CFixedVector2D(it->second.x, it->second.z), it->second.height); else - LosAdd(it->second.owner, it->second.visionRange, CFixedVector2D(it->second.x, it->second.z)); + LosAdd(it->second.owner, it->second.visionRange, CFixedVector2D(it->second.x, it->second.z), it->second.height); AddToTile(PosToLosTilesHelper(it->second.x, it->second.z), it->first); if (it->second.HasFlag()) - RevealShore(it->second.owner, true); + RevealShore(it->second.owner, true, it->second.height); } m_TotalInworldVertices = 0; @@ -1584,6 +1636,13 @@ it->second.SetFlag(status); } + virtual bool TestVisibility(int i, int j, player_id_t player, ELosState state) const + { + if (LosIsOffWorld(i, j) || !(i >= 0 && j >= 0 && i < m_TerrainVerticesPerSide && j < m_TerrainVerticesPerSide)) + return false; + return m_LosState[j*m_TerrainVerticesPerSide + i] & (state << (2 * (player - 1))); + } + ELosVisibility ComputeLosVisibility(CEntityHandle ent, player_id_t player) const { // Entities not with positions in the world are never visible @@ -1599,8 +1658,8 @@ return VIS_HIDDEN; CFixedVector2D pos = cmpPosition->GetPosition2D(); - int i = (pos.X / (int)TERRAIN_TILE_SIZE).ToInt_RoundToNearest(); - int j = (pos.Y / (int)TERRAIN_TILE_SIZE).ToInt_RoundToNearest(); + int i = (pos.X / static_cast(TERRAIN_TILE_SIZE)).ToInt_RoundToNearest(); + int j = (pos.Y / static_cast(TERRAIN_TILE_SIZE)).ToInt_RoundToNearest(); // Reveal flag makes all positioned entities visible and all mirages useless if (GetLosRevealAll(player)) @@ -1837,6 +1896,12 @@ UpdateVisibility(ent, player); } + virtual void SetVisionBlockingEnabled(bool enabled) + { + debug_printf("set vision blocking to %d from %d\n", enabled, m_VisionBlocked); + m_VisionBlockingEnabled = enabled; + } + virtual void SetLosRevealAll(player_id_t player, bool enabled) { if (player == -1) @@ -2008,7 +2073,7 @@ } } - virtual void RevealShore(player_id_t p, bool enable) + virtual void RevealShore(player_id_t p, bool enable, u16 height) { if (p <= 0 || p > MAX_LOS_PLAYER_ID) return; @@ -2032,10 +2097,7 @@ continue; // Maybe we could be more clever and don't add dummy strips of one tile - if (enable) - LosAddStripHelper(p, i, i, j, countsData); - else - LosRemoveStripHelper(p, i, i, j, countsData); + LosManageStripHelper(enable, p, i, i, j, countsData, height, i, j); } } @@ -2058,74 +2120,450 @@ return (dist2 >= r*r); } - else - { - // With a square map, the outermost edge of the map should be off-world, - // so the SoD texture blends out nicely - return i < MAP_EDGE_TILES || j < MAP_EDGE_TILES || - i >= m_TerrainVerticesPerSide - MAP_EDGE_TILES || - j >= m_TerrainVerticesPerSide - MAP_EDGE_TILES; - } + + // With a square map, the outermost edge of the map should be off-world, + // so the SoD texture blends out nicely + return i < MAP_EDGE_TILES || j < MAP_EDGE_TILES || + i >= m_TerrainVerticesPerSide - MAP_EDGE_TILES || + j >= m_TerrainVerticesPerSide - MAP_EDGE_TILES; } /** - * Update the LOS state of tiles within a given horizontal strip (i0,j) to (i1,j) (inclusive). + * Returns true iff both tiles (a1, b1), (a2, b2) are visible from source + * Using visibility map */ - inline void LosAddStripHelper(u8 owner, i32 i0, i32 i1, i32 j, u16* counts) + inline bool CheckTilesForVisibility(i32 a1, i32 b1, i32 a2, i32 b2) { - if (i1 < i0) - return; + #if DEBUG_VIS_COMP + ENSURE(b1 > -1); + ENSURE(a1 > -1); + ENSURE(b2 > -1); + ENSURE(a2 > -1); + #endif + i32 idx = (b1)*m_TerrainVerticesPerSide + (a1); + i32 idx2 = (b2)*m_TerrainVerticesPerSide + (a2); + #if DEBUG_VIS_COMP + ENSURE(m_VisComputedBefore[idx]); + ENSURE(m_VisComputedBefore[idx2]); + #endif + return m_Vismap[idx] && m_Vismap[idx2]; + } - i32 idx0 = j*m_TerrainVerticesPerSide + i0; - i32 idx1 = j*m_TerrainVerticesPerSide + i1; - u32 &explored = m_ExploredVertices.at(owner); - for (i32 idx = idx0; idx <= idx1; ++idx) + /** + * Check if at least one of tiles (a1, b1), (a2, b2) + * is was higher then source + * Using blocking vision map + */ + inline bool AreTilesHigher(i32 a1, i32 b1, i32 a2, i32 b2) + { + i32 idx = (b1)*m_TerrainVerticesPerSide + (a1); + i32 idx2 = (b2)*m_TerrainVerticesPerSide + (a2); + return m_IsBlockingVision[idx] || m_IsBlockingVision[idx2]; + } + +#if DEBUG_VIS_COMP + #define ensurecomputedbefore(x) \ + {\ + ENSURE(m_VisComputedBefore[idx]);\ + } +#else + #define ensurecomputedbefore(x) +#endif + /** + * Returns true if tile (i, j) is visible from given starting tile (iFrom, jFrom) + * Every tile above given height (hFrom) will block vision + * This is using global visibility map and blocking vision map + * so correct computation requires to check all tiles closer to source first + * Source tile is allways marked as visible and has to be checked + * This is using m_VisionBlocked to know if there was + * blocking of vision in previous computations + * Has to be called from single thread + * @param {idxx} position of (i, j) in visibility map + */ + inline bool IsVisibleTile(i32 iFrom, i32 jFrom, float hFrom, i32 i, i32 j, i32 idxx) + { + // Zero: The same tile is allways visible + if (iFrom == i && jFrom == j) { - // Increasing from zero to non-zero - move from unexplored/explored to visible+explored - if (counts[idx] == 0) - { - i32 i = i0 + idx - idx0; - if (!LosIsOffWorld(i, j)) - { - explored += !(m_LosState[idx] & (LOS_EXPLORED << (2*(owner-1)))); - m_LosState[idx] |= ((LOS_VISIBLE | LOS_EXPLORED) << (2*(owner-1))); - } + m_IsBlockingVision[idxx] = false; + return true; + } - MarkVisibilityDirtyAroundTile(owner, i, j); - } + // First: Check if we see it by high difference + float h2 = m_Terrain->GetVertexGroundLevel(i, j); + m_IsBlockingVision[idxx] = hFrom < h2; + if (m_IsBlockingVision[idxx]) + m_VisionBlocked = true; + + // Vision was not blocked yet so abort + if (!m_VisionBlocked) + return true; - ASSERT(counts[idx] < 65535); - counts[idx] = (u16)(counts[idx] + 1); // ignore overflow; the player should never have 64K units + float h3 = 0; + // Check distances + i32 iDistA = std::abs(iFrom - i); + i32 jDistA = std::abs(jFrom - j); + i32 idx; + + #if DEBUG_VIS_COMP + ENSURE(i > 0); + ENSURE(j > 0); + ENSURE(iFrom > 0); + ENSURE(jFrom > 0); + ENSURE(i < m_TerrainVerticesPerSide); + ENSURE(j < m_TerrainVerticesPerSide); + ENSURE(iFrom < m_TerrainVerticesPerSide); + ENSURE(jFrom < m_TerrainVerticesPerSide); + #endif + + // Second: Check if tile before is visible + // 1) straight vision - check tiles at line (and return right away) + // 1.1) check on i line + if (i == iFrom) + { + // 1.1.a) we are down so check to up + if (j < jFrom) + { + idx = (j + 1)*m_TerrainVerticesPerSide + i; + ensurecomputedbefore(idx); + if (!m_Vismap[idx]) + return false; + // tile before is visible + if (!m_IsBlockingVision[idx]) + return true; + // tile before is blocking vision + h3 = m_Terrain->GetVertexGroundLevel(i, j + 1); + return h2 - h3 > 1; + } + // 1.1.b) we are up so check to down + if (j > jFrom) + { + idx = (j - 1)*m_TerrainVerticesPerSide + i; + ensurecomputedbefore(idx); + if (!m_Vismap[idx]) + return false; + if (!m_IsBlockingVision[idx]) + return true; + h3 = m_Terrain->GetVertexGroundLevel(i, j - 1); + return h2 - h3 > 1; + } + } + // 1.2) check on j line + else if (j == jFrom) + { + // 1.2.a) we are left so check to right + if (i < iFrom) { + idx = j*m_TerrainVerticesPerSide + (i + 1); + ensurecomputedbefore(idx); + if (!m_Vismap[idx]) + return false; + if (!m_IsBlockingVision[idx]) + return true; + h3 = m_Terrain->GetVertexGroundLevel(i + 1, j); + return h2 - h3 > 1; + } + // 1.2.b) we are right so check to left + if (i > iFrom) + { + idx = j*m_TerrainVerticesPerSide + (i - 1); + ensurecomputedbefore(idx); + if (!m_Vismap[idx]) + return false; + if (!m_IsBlockingVision[idx]) + return true; + h3 = m_Terrain->GetVertexGroundLevel(i - 1, j); + return h2 - h3 > 1; + } + } + // 2) check diagonals to bottom + else if (j < jFrom) + { + // 2.1) check diagonals to bottom right + if (i > iFrom) + { + // 2.1.a) true diagonal + // - check only next diagonal tile + if (iDistA == jDistA) + { + idx = (j + 1)*m_TerrainVerticesPerSide + (i - 1); + ensurecomputedbefore(idx); + if (!m_Vismap[idx]) + return false; + if (!m_IsBlockingVision[idx]) + return true; + h3 = m_Terrain->GetVertexGroundLevel(i - 1, j + 1); + return h2 - h3 > 1; + } + // 2.1.b) we are under so check to top and top left + else if (jDistA > iDistA) + { + if (!CheckTilesForVisibility(i, j + 1, i - 1, j + 1)) + return false; + // Tiles before are visible + if (!AreTilesHigher(i, j + 1, i - 1, j + 1)) + return true; + // Tiles before are blocking vision + h3 = m_Terrain->GetVertexGroundLevel(i, j + 1); + if (h2 - h3 <= 1) + return false; + h3 = m_Terrain->GetVertexGroundLevel(i - 1, j + 1); + return h2 - h3 > 1; + } + // 2.1.c) we are up so check to left and left top + else if (jDistA < iDistA) + { + if (!CheckTilesForVisibility(i - 1, j, i - 1, j + 1)) + return false; + if (!AreTilesHigher(i - 1, j, i - 1, j + 1)) + return true; + h3 = m_Terrain->GetVertexGroundLevel(i - 1, j); + if (h2 - h3 <= 1) + return false; + h3 = m_Terrain->GetVertexGroundLevel(i - 1, j + 1); + return h2 - h3 > 1; + } + } + // 2.2) check diagonals to bottom left + else if (i < iFrom) + { + // 2.2.a) true diagonal + // - check only next diagonal tile + if (iDistA == jDistA) + { + idx = (j + 1)*m_TerrainVerticesPerSide + (i + 1); + ensurecomputedbefore(idx); + if (!m_Vismap[idx]) + return false; + if (!m_IsBlockingVision[idx]) + return true; + h3 = m_Terrain->GetVertexGroundLevel(i + 1, j + 1); + return h2 - h3 > 1; + } + // 2.2.b) we are under so check to top and top right + else if (jDistA > iDistA) + { + if (!CheckTilesForVisibility(i, j + 1, i + 1, j + 1)) + return false; + if (!AreTilesHigher(i, j + 1, i + 1, j + 1)) + return true; + h3 = m_Terrain->GetVertexGroundLevel(i, j + 1); + if (h2 - h3 <= 1) + return false; + h3 = m_Terrain->GetVertexGroundLevel(i + 1, j + 1); + return h2 - h3 > 1; + } + // 2.2.c) we are up so check to right and right top + else if (jDistA < iDistA) + { + if (!CheckTilesForVisibility(i + 1, j, i + 1, j + 1)) + return false; + if (!AreTilesHigher(i + 1, j, i + 1, j + 1)) + return true; + h3 = m_Terrain->GetVertexGroundLevel(i + 1, j); + if (h2 - h3 <= 1) + return false; + h3 = m_Terrain->GetVertexGroundLevel(i + 1, j + 1); + return h2 - h3 > 1; + } + } + } + // 3) check diagonals to top + else if (j > jFrom) + { + // 3.1) check diagonals to top right + if (i > iFrom) + { + // 3.1.a) true diagonal + // - check only next diagonal tile + if (iDistA == jDistA) + { + idx = (j - 1)*m_TerrainVerticesPerSide + (i - 1); + ensurecomputedbefore(idx); + if (!m_Vismap[idx]) + return false; + if (!m_IsBlockingVision[idx]) + return true; + h3 = m_Terrain->GetVertexGroundLevel(i - 1, j - 1); + return h2 - h3 > 1; + } + // 3.1.b) we are up so check down and down left + else if (jDistA < iDistA) + { + if (!CheckTilesForVisibility(i - 1, j, i - 1, j - 1)) + return false; + if (!AreTilesHigher(i - 1, j, i - 1, j - 1)) + return true; + h3 = m_Terrain->GetVertexGroundLevel(i - 1, j); + if (h2 - h3 <= 1) + return false; + h3 = m_Terrain->GetVertexGroundLevel(i - 1, j - 1); + return h2 - h3 > 1; + } + // 3.1.c) we are under so check to left and left down + else if (jDistA > iDistA) + { + if (!CheckTilesForVisibility(i, j - 1, i - 1, j - 1)) + return false; + if (!AreTilesHigher(i, j - 1, i - 1, j - 1)) + return true; + h3 = m_Terrain->GetVertexGroundLevel(i, j - 1); + if (h2 - h3 <= 1) + return false; + h3 = m_Terrain->GetVertexGroundLevel(i - 1, j - 1); + return h2 - h3 > 1; + } + } + // 3.2) check diagonals to top left + else if (i < iFrom) + {// + // 3.2.a) true diagonal + // - check only next diagonal tile + if (iDistA == jDistA) + { + idx = (j - 1)*m_TerrainVerticesPerSide + (i + 1); + ensurecomputedbefore(idx); + if (!m_Vismap[idx]) + return false; + if (!m_IsBlockingVision[idx]) + return true; + h3 = m_Terrain->GetVertexGroundLevel(i + 1, j - 1); + return h2 - h3 > 1; + } + // 3.2.b) we are down so check to right and down right + else if (jDistA < iDistA) + { + if (!CheckTilesForVisibility(i + 1, j, i + 1, j - 1)) + return false; + if (!AreTilesHigher(i + 1, j, i + 1, j - 1)) + return true; + h3 = m_Terrain->GetVertexGroundLevel(i + 1, j); + if (h2 - h3 <= 1) + return false; + h3 = m_Terrain->GetVertexGroundLevel(i + 1, j - 1); + return h2 - h3 > 1; + } + // 3.2.c) we are up so check to right and right down + else if (jDistA > iDistA) + { + if (!CheckTilesForVisibility(i, j - 1, i + 1, j - 1)) + return false; + if (!AreTilesHigher(i, j - 1, i + 1, j - 1)) + return true; + h3 = m_Terrain->GetVertexGroundLevel(i, j - 1); + if (h2 - h3 <= 1) + return false; + h3 = m_Terrain->GetVertexGroundLevel(i + 1, j - 1); + return h2 - h3 > 1; + } + } + } + return true; + } + /** + * Check if tile is visible from given tile taking direction into account + * This is updating visibility map shared among all tiles so make sure + * this is called only from one thread + * @param iFrom position from starting tile + * @param jFrom position from starting tile + * @param hFrom height tiles higher than this will block visibility + * @param i position of tile we are checking + * @param j position of tile we are checking + * @param idx index of checking position in visibility map + * @return true iff given tile is visible + */ + inline bool IsVisibleTileMark(i32 iFrom, i32 jFrom, float hFrom, i32 i, i32 j, i32 idx) + { + #if DEBUG_VIS_COMP + if (m_VisComputedBefore.empty()) + { + m_VisComputedBefore.resize(m_TerrainVerticesPerSide*m_TerrainVerticesPerSide); + ENSURE(!m_VisComputedBefore[1]); + } + #endif + // not visible if off world + // if is of world do not bother updating visibility map + // there will be allways false + if (LosIsOffWorld(i, j)) + { + #if DEBUG_VIS_COMP + if (i > -1 && j > -1 && idx < m_VisComputedBefore.size()) { + m_VisComputedBefore[idx] = true; + ENSURE(m_VisComputedBefore[idx]); + } + #endif + return false; } + if (!m_Terrain) + return true; + m_Vismap[idx] = IsVisibleTile(iFrom, jFrom, hFrom, i, j, idx); + #if DEBUG_VIS_COMP + m_VisComputedBefore[idx] = true; + ENSURE(m_VisComputedBefore[idx]); + #endif + return m_Vismap[idx]; } /** - * Update the LOS state of tiles within a given horizontal strip (i0,j) to (i1,j) (inclusive). + * Update the LOS state of tiles within a given horizontal strip (i0,j) to (i1,j) (inclusive) + * Looking from tile (x, y) from height h + * @see IsVisibleTileMark */ - inline void LosRemoveStripHelper(u8 owner, i32 i0, i32 i1, i32 j, u16* counts) + inline void LosManageStripHelper(bool add, u8 owner, i32 i0, i32 i1, i32 j, u16* counts, float heigth = 0, i32 x = 0, i32 y = 0) { if (i1 < i0) return; i32 idx0 = j*m_TerrainVerticesPerSide + i0; i32 idx1 = j*m_TerrainVerticesPerSide + i1; + u32 &explored = m_ExploredVertices.at(owner); for (i32 idx = idx0; idx <= idx1; ++idx) { - ASSERT(counts[idx] > 0); - counts[idx] = (u16)(counts[idx] - 1); - - // Decreasing from non-zero to zero - move from visible+explored to explored - if (counts[idx] == 0) + i32 i = i0 + idx - idx0; + if (m_VisionBlockingEnabled && !IsVisibleTileMark(x, y, heigth, i, j, idx)) + continue; + if (add) { - // (If LosIsOffWorld then this is a no-op, so don't bother doing the check) - m_LosState[idx] &= ~(LOS_VISIBLE << (2*(owner-1))); - - i32 i = i0 + idx - idx0; - MarkVisibilityDirtyAroundTile(owner, i, j); + // Increasing from zero to non-zero - move from unexplored/explored to visible+explored + if (counts[idx] == 0) + { + i32 i = i0 + idx - idx0; + if (!LosIsOffWorld(i, j)) + { + explored += !(m_LosState[idx] & (LOS_EXPLORED << (2 * (owner - 1)))); + m_LosState[idx] |= ((LOS_VISIBLE | LOS_EXPLORED) << (2 * (owner - 1))); + } + MarkVisibilityDirtyAroundTile(owner, i, j); + } + ENSURE(counts[idx] < 65535); + counts[idx] = (u16)(counts[idx] + 1); // ignore overflow; the player should never have 64K units + } + else + { + if (counts[idx]) + { + counts[idx] = (u16)(counts[idx] - 1); + // Decreasing from non-zero to zero - move from visible+explored to explored + if (counts[idx] == 0) + { + m_LosState[idx] &= ~(LOS_VISIBLE << (2 * (owner - 1))); + MarkVisibilityDirtyAroundTile(owner, i, j); + } + ENSURE(counts[idx] > -1); + } } } } + /** + * Inverted function compared to LosManagerStripHelper iterating from (i, j0) to (i, j1) + * @see IsVisibleTileMark + */ + inline void LosManageStripHelperJ(bool add, u8 owner, i32 j0, i32 j1, i32 i, u16* counts, float h, i32 x, i32 y) + { + for (i32 j = j0; j <= j1; ++j) + LosManageStripHelper(add, owner, i, i, j, counts, h, x, y); + } + inline void MarkVisibilityDirtyAroundTile(u8 owner, i32 i, i32 j) { // If we're still in the deserializing process, we must not modify m_DirtyVisibility @@ -2155,6 +2593,168 @@ * Update the LOS state of tiles within a given circular range, * either adding or removing visibility depending on the template parameter. * Assumes owner is in the valid range. + * Provide vision blocking by terrain. + * Height (eH) is added to ground/water level. + */ + template + void LosBlockingUpdateHelper(u8 owner, entity_pos_t visionRange, CFixedVector2D pos, u16 eH) + { + if (!m_VisionBlockingEnabled) + { + LosUpdateHelper((u8)owner, visionRange, pos); + return; + } + if (!m_Terrain) + { + CmpPtr cmpTerrain(GetSimContext(), SYSTEM_ENTITY); + if (cmpTerrain) + m_Terrain = cmpTerrain->GetCTerrain(); + ENSURE(m_Terrain); + } + // Do nothing if not initialised yet. + if (m_TerrainVerticesPerSide == 0) + return; + PROFILE("LosBlockingUpdateHelper"); + + std::vector& counts = m_LosPlayerCounts.at(owner); + + // Lazy initialisation of counts: + if (counts.empty()) + counts.resize(m_TerrainVerticesPerSide*m_TerrainVerticesPerSide); + + u16* countsData = &counts[0]; + // Create empty vision map if needed. + if (m_Vismap.empty()) + m_Vismap.resize(m_TerrainVerticesPerSide*m_TerrainVerticesPerSide); + // Create empty blocking map if needed. + if (m_IsBlockingVision.empty()) + m_IsBlockingVision.resize(m_TerrainVerticesPerSide*m_TerrainVerticesPerSide); + + // Reset this as we are starting new detection. + m_VisionBlocked = false; + // Translate world coordinates into fractional tile-space coordinates. + entity_pos_t x = pos.X / static_cast(TERRAIN_TILE_SIZE); + entity_pos_t y = pos.Y / static_cast(TERRAIN_TILE_SIZE); + entity_pos_t r = visionRange / static_cast(TERRAIN_TILE_SIZE); + entity_pos_t r2 = r.Square(); + + i32 xfloor = (x - entity_pos_t::Epsilon()).ToInt_RoundToNegInfinity(); + i32 yfloor = (y - entity_pos_t::Epsilon()).ToInt_RoundToNegInfinity(); + i32 rfloor = (r - entity_pos_t::Epsilon()).ToInt_RoundToNegInfinity(); + + #if DEBUG_VIS_COMP + m_VisComputedBefore.resize(m_TerrainVerticesPerSide*m_TerrainVerticesPerSide); + ENSURE(!m_VisComputedBefore[1]); + ENSURE(m_VisComputedBefore.size() == m_TerrainVerticesPerSide*m_TerrainVerticesPerSide); + #endif + // Do nothing if of world. + if (LosIsOffWorld(xfloor, yfloor)) + { + #if DEBUG_VIS_COMP + i32 idxd = yfloor*m_TerrainVerticesPerSide + xfloor; + m_VisComputedBefore[idxd] = true; + ENSURE(m_VisComputedBefore[idxd]); + #endif + return; + } + // Get height of terrain/water at entity position. + float h = 0.0; + h = m_Terrain->GetVertexGroundLevel(xfloor, yfloor); + + CmpPtr cmpWaterManager(GetSystemEntity()); + if (cmpWaterManager) { + float wl = cmpWaterManager->GetWaterLevel(pos.X, pos.Y).ToFloat(); + if (wl > h) + h = wl; + } + // Add entity heigth. + h = h + eH; + + // Direction of incrementation of square. + i32 ipp = 1; + // Guess how many tiles we should check at squre side. + // Incremented by ipp at each step. + i32 ip = 0; + // Incrementally make squares larger. + for (i32 range = 0; range < rfloor + 4; ++range) { + // This defines square with side 2*range + // and centre at entity position. + i32 i0 = xfloor - range; + i32 i1 = xfloor + range; + i32 j0 = yfloor - range; + i32 j1 = yfloor + range; + + // This defines which tiles at given + // square we have to check. + i32 ifrom = xfloor - ip; + i32 ito = xfloor + ip; + // We cut corners so we do not check twice. + i32 jfrom = yfloor - ip + 1; + i32 jto = yfloor + ip - 1; + entity_pos_t dy; + entity_pos_t dy2; + if (ipp > 0) { + dy = entity_pos_t::FromInt(range + 1); + dy2 = dy.Square(); + // We have filled square and half length of diagonal is larger + // than vision range so invert direction. + if (dy2 + dy2 > r2) + ipp = -1; + } + else if (ipp < 0) { + dy = entity_pos_t::FromInt(range); + dy2 = dy.Square(); + // We went out of vision range so abort. + if (dy2 > r2) + break; + } + // We might overshoot vision range so make it more looks like circle. + while (ifrom < xfloor && dy2 + (entity_pos_t::FromInt(ifrom) - x).Square() > r2) + ifrom++; + while (ito > xfloor + 1 && dy2 + (entity_pos_t::FromInt(ito) - x).Square() > r2) + ito--; + while (jfrom < yfloor && dy2 + (entity_pos_t::FromInt(jfrom) - y).Square() > r2) + jfrom++; + while (jto > yfloor + 1 && dy2 + (entity_pos_t::FromInt(jto) - y).Square() > r2) + jto--; + + ip = ip + ipp; + // Keep square envelope cordinates in map. + i0 = std::max(i0, 1); + i1 = std::min(i1, m_TerrainVerticesPerSide - 2); + j0 = std::max(j0, 1); + j1 = std::min(j1, m_TerrainVerticesPerSide - 2); + // The same for side cuts. + ifrom = std::max(ifrom, 1); + ito = std::min(ito, m_TerrainVerticesPerSide - 2); + jfrom = std::max(jfrom, 1); + jto = std::min(jto, m_TerrainVerticesPerSide - 2); + + // First check bottom line. + LosManageStripHelper(adding, owner, ifrom, ito, j0, countsData, h, xfloor, yfloor); + // Check top line. + if (j0 != j1) + LosManageStripHelper(adding, owner, ifrom, ito, j1, countsData, h, xfloor, yfloor); + // Make sure jfrom is not greather than jto because of cutting corners. + if (jfrom <= jto) { + // Now check remaining tiles at left side of square. + LosManageStripHelperJ(adding, owner, jfrom, jto, i0, countsData, h, xfloor, yfloor); + // At last do the check for tiles at right side of square. + if (i0 != i1) + LosManageStripHelperJ(adding, owner, jfrom, jto, i1, countsData, h, xfloor, yfloor); + } + + // We have no more tiles to check. + if (ip < 1) + break; + } + } + + + /** + * Update the LOS state of tiles within a given circular range, + * either adding or removing visibility depending on the template parameter. + * Assumes owner is in the valid range. */ template void LosUpdateHelper(u8 owner, entity_pos_t visionRange, CFixedVector2D pos) @@ -2234,10 +2834,7 @@ // then add or remove the strip as requested i32 i0clamp = std::max(i0, 1); i32 i1clamp = std::min(i1, m_TerrainVerticesPerSide-2); - if (adding) - LosAddStripHelper(owner, i0clamp, i1clamp, j, countsData); - else - LosRemoveStripHelper(owner, i0clamp, i1clamp, j, countsData); + LosManageStripHelper(adding, owner, i0clamp, i1clamp, j, countsData); } } @@ -2345,11 +2942,11 @@ // and we can just add/remove the entire other strip if (i1clamp_from < i0clamp_from) { - LosAddStripHelper(owner, i0clamp_to, i1clamp_to, j, countsData); + LosManageStripHelper(true, owner, i0clamp_to, i1clamp_to, j, countsData); } else if (i1clamp_to < i0clamp_to) { - LosRemoveStripHelper(owner, i0clamp_from, i1clamp_from, j, countsData); + LosManageStripHelper(false, owner, i0clamp_from, i1clamp_from, j, countsData); } else { @@ -2362,56 +2959,64 @@ // movement speeds), the region between them will be both added and removed, // so we have to do the add first to avoid overflowing to -1 and triggering // assertion failures.) - LosAddStripHelper(owner, i0clamp_to, i0clamp_from-1, j, countsData); - LosAddStripHelper(owner, i1clamp_from+1, i1clamp_to, j, countsData); - LosRemoveStripHelper(owner, i0clamp_from, i0clamp_to-1, j, countsData); - LosRemoveStripHelper(owner, i1clamp_to+1, i1clamp_from, j, countsData); + LosManageStripHelper(true, owner, i0clamp_to, i0clamp_from-1, j, countsData); + LosManageStripHelper(true, owner, i1clamp_from+1, i1clamp_to, j, countsData); + LosManageStripHelper(false, owner, i0clamp_from, i0clamp_to-1, j, countsData); + LosManageStripHelper(false, owner, i1clamp_to+1, i1clamp_from, j, countsData); } } } } - void LosAdd(player_id_t owner, entity_pos_t visionRange, CFixedVector2D pos) + void LosAdd(player_id_t owner, entity_pos_t visionRange, CFixedVector2D pos, u16 height) { if (visionRange.IsZero() || owner <= 0 || owner > MAX_LOS_PLAYER_ID) return; - LosUpdateHelper((u8)owner, visionRange, pos); + LosBlockingUpdateHelper((u8)owner, visionRange, pos, height); } - void SharingLosAdd(u16 visionSharing, entity_pos_t visionRange, CFixedVector2D pos) + void SharingLosAdd(u16 visionSharing, entity_pos_t visionRange, CFixedVector2D pos, u16 height) { if (visionRange.IsZero()) return; for (player_id_t i = 1; i < MAX_LOS_PLAYER_ID+1; ++i) if (HasVisionSharing(visionSharing, i)) - LosAdd(i, visionRange, pos); + LosAdd(i, visionRange, pos, height); } - void LosRemove(player_id_t owner, entity_pos_t visionRange, CFixedVector2D pos) + void LosRemove(player_id_t owner, entity_pos_t visionRange, CFixedVector2D pos, u16 height) { if (visionRange.IsZero() || owner <= 0 || owner > MAX_LOS_PLAYER_ID) return; - LosUpdateHelper((u8)owner, visionRange, pos); + LosBlockingUpdateHelper((u8)owner, visionRange, pos, height); } - void SharingLosRemove(u16 visionSharing, entity_pos_t visionRange, CFixedVector2D pos) + void SharingLosRemove(u16 visionSharing, entity_pos_t visionRange, CFixedVector2D pos, u16 height) { if (visionRange.IsZero()) return; for (player_id_t i = 1; i < MAX_LOS_PLAYER_ID+1; ++i) if (HasVisionSharing(visionSharing, i)) - LosRemove(i, visionRange, pos); + LosRemove(i, visionRange, pos, height); } - void LosMove(player_id_t owner, entity_pos_t visionRange, CFixedVector2D from, CFixedVector2D to) + void LosMove(player_id_t owner, entity_pos_t visionRange, CFixedVector2D from, CFixedVector2D to, u16 heigth) { if (visionRange.IsZero() || owner <= 0 || owner > MAX_LOS_PLAYER_ID) return; + // Vision blocking does not have incremental variant. + if (m_VisionBlockingEnabled) + { + LosBlockingUpdateHelper((u8)owner, visionRange, from, heigth); + LosBlockingUpdateHelper((u8)owner, visionRange, to, heigth); + return; + } + if ((from - to).CompareLength(visionRange) > 0) { // If it's a very large move, then simply remove and add to the new position @@ -2423,14 +3028,14 @@ LosUpdateHelperIncremental((u8)owner, visionRange, from, to); } - void SharingLosMove(u16 visionSharing, entity_pos_t visionRange, CFixedVector2D from, CFixedVector2D to) + void SharingLosMove(u16 visionSharing, entity_pos_t visionRange, CFixedVector2D from, CFixedVector2D to, u16 height) { if (visionRange.IsZero()) return; for (player_id_t i = 1; i < MAX_LOS_PLAYER_ID+1; ++i) if (HasVisionSharing(visionSharing, i)) - LosMove(i, visionRange, from, to); + LosMove(i, visionRange, from, to, height); } virtual u8 GetPercentMapExplored(player_id_t player) const @@ -2438,13 +3043,18 @@ return m_ExploredVertices.at((u8)player) * 100 / m_TotalInworldVertices; } + virtual u32 GetExploredVertices(player_id_t player) const + { + return m_ExploredVertices.at((u8)player); + } + virtual u8 GetUnionPercentMapExplored(const std::vector& players) const { u32 exploredVertices = 0; std::vector::const_iterator playerIt; - for (i32 j = 0; j < m_TerrainVerticesPerSide; j++) - for (i32 i = 0; i < m_TerrainVerticesPerSide; i++) + for (i32 j = 0; j < m_TerrainVerticesPerSide; ++j) + for (i32 i = 0; i < m_TerrainVerticesPerSide; ++i) { if (LosIsOffWorld(i, j)) continue; Index: source/simulation2/components/ICmpFootprint.h =================================================================== --- source/simulation2/components/ICmpFootprint.h +++ source/simulation2/components/ICmpFootprint.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2017 Wildfire Games. +/* Copyright (C) 2019 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. is free software: you can redistribute it and/or modify @@ -56,6 +56,8 @@ */ JS::Value GetShape_wrapper() const; + virtual entity_pos_t GetHeight() const = 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 Index: source/simulation2/components/ICmpFootprint.cpp =================================================================== --- source/simulation2/components/ICmpFootprint.cpp +++ source/simulation2/components/ICmpFootprint.cpp @@ -1,4 +1,4 @@ -/* Copyright (C) 2017 Wildfire Games. +/* Copyright (C) 2019 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. is free software: you can redistribute it and/or modify @@ -71,5 +71,6 @@ BEGIN_INTERFACE_WRAPPER(Footprint) DEFINE_INTERFACE_METHOD_CONST_1("PickSpawnPoint", CFixedVector3D, ICmpFootprint, PickSpawnPoint, entity_id_t) DEFINE_INTERFACE_METHOD_CONST_1("PickSpawnPointBothPass", CFixedVector3D, ICmpFootprint, PickSpawnPointBothPass, entity_id_t) +DEFINE_INTERFACE_METHOD_CONST_0("GetHeight", entity_pos_t, ICmpFootprint,GetHeight) DEFINE_INTERFACE_METHOD_CONST_0("GetShape", JS::Value, ICmpFootprint, GetShape_wrapper) END_INTERFACE_WRAPPER(Footprint) Index: source/simulation2/components/ICmpRangeManager.h =================================================================== --- source/simulation2/components/ICmpRangeManager.h +++ source/simulation2/components/ICmpRangeManager.h @@ -387,7 +387,7 @@ * will be necessary to call it the same number of times with !enabled to make the shore * fall back into the FoW. */ - virtual void RevealShore(player_id_t p, bool enable) = 0; + virtual void RevealShore(player_id_t p, bool enable, u16 h) = 0; /** * Set whether the whole map should be made visible to the given player. @@ -396,6 +396,11 @@ virtual void SetLosRevealAll(player_id_t player, bool enabled) = 0; /** + * Set whether vision is blocked by terrain. + */ + virtual void SetVisionBlockingEnabled(bool enabled) = 0; + + /** * Returns whether the whole map has been made visible to the given player. */ virtual bool GetLosRevealAll(player_id_t player) const = 0; @@ -437,6 +442,17 @@ */ virtual void Verify() = 0; + /* + * Return if tile with given coordinates has given los state for player + * Used by tests + */ + virtual bool TestVisibility(int i, int j, player_id_t player, ELosState state) const = 0; + + /** + * Get amount of explored vertices by player + * Used by tests + */ + virtual u32 GetExploredVertices(player_id_t player) const = 0; DECLARE_INTERFACE_TYPE(RangeManager) }; Index: source/simulation2/components/tests/test_RangeManager.h =================================================================== --- source/simulation2/components/tests/test_RangeManager.h +++ source/simulation2/components/tests/test_RangeManager.h @@ -17,26 +17,63 @@ #include "simulation2/system/ComponentTest.h" #include "simulation2/components/ICmpRangeManager.h" +#include "simulation2/components/ICmpWaterManager.h" #include "simulation2/components/ICmpPosition.h" #include "simulation2/components/ICmpVision.h" +#include "simulation2/components/ICmpFootprint.h" +#include "simulation2/components/ICmpOwnership.h" + +#include "graphics/Terrain.h" +#include "simulation2/helpers/Geometry.h" #include #include +class MockOwnership : public ICmpOwnership +{ + private: + player_id_t m_Owner; + public: + virtual int GetComponentTypeId() const { return IID_Ownership; } + virtual void Init(const CParamNode& UNUSED(paramNode)) { } + virtual void Deinit() {} + virtual void Serialize(ISerializer& UNUSED(serialize)) { } + virtual void Deserialize(const CParamNode& paramNode, IDeserializer& UNUSED(deserialize)) + { Init(paramNode);} + virtual void SetOwner(player_id_t owner) { m_Owner = owner; } + virtual player_id_t GetOwner() const { return m_Owner; }; + virtual void SetOwnerQuiet(player_id_t owner) { m_Owner = owner; } +}; + class MockVision : public ICmpVision { +private: + entity_pos_t m_Range; public: - DEFAULT_MOCK_COMPONENT() - - virtual entity_pos_t GetRange() const { return entity_pos_t::FromInt(66); } + virtual int GetComponentTypeId() const { return IID_Vision; } + virtual void Init(const CParamNode& UNUSED(paramNode)) { } + virtual void Deinit() {} + virtual void Serialize(ISerializer& UNUSED(serialize)) { } + virtual void Deserialize(const CParamNode& paramNode, IDeserializer& UNUSED(deserialize)) + { Init(paramNode); } + virtual void SetRange(entity_pos_t range) { m_Range = range; } + virtual entity_pos_t GetRange() const { return m_Range; } virtual bool GetRevealShore() const { return false; } }; class MockPosition : public ICmpPosition { +private: + CFixedVector2D m_Pos2d; public: - DEFAULT_MOCK_COMPONENT() + virtual int GetComponentTypeId() const { return IID_Position; } + virtual void Init(const CParamNode& UNUSED(paramNode)) { } + virtual void Deinit() {} + virtual void Serialize(ISerializer& UNUSED(serialize)) { } + virtual void Deserialize(const CParamNode& paramNode, IDeserializer& UNUSED(deserialize)) + { Init(paramNode); } + virtual void SetPosition(entity_pos_t x, entity_pos_t y) { m_Pos2d.X = x; m_Pos2d.Y = y;} virtual void SetTurretParent(entity_id_t UNUSED(id), const CFixedVector3D& UNUSED(pos)) {} virtual entity_id_t GetTurretParent() const {return INVALID_ENTITY;} virtual void UpdateTurretPosition() {} @@ -57,7 +94,7 @@ virtual void SetActorFloating(bool UNUSED(flag)) { } virtual void SetConstructionProgress(fixed UNUSED(progress)) { } virtual CFixedVector3D GetPosition() const { return CFixedVector3D(); } - virtual CFixedVector2D GetPosition2D() const { return CFixedVector2D(); } + virtual CFixedVector2D GetPosition2D() const { return m_Pos2d; } virtual CFixedVector3D GetPreviousPosition() const { return CFixedVector3D(); } virtual CFixedVector2D GetPreviousPosition2D() const { return CFixedVector2D(); } virtual void TurnTo(entity_angle_t UNUSED(y)) { } @@ -69,6 +106,188 @@ virtual CMatrix3D GetInterpolatedTransform(float UNUSED(frameOffset)) const { return CMatrix3D(); } }; +class MockWater : public ICmpWaterManager +{ +public: + DEFAULT_MOCK_COMPONENT() + + virtual entity_pos_t GetWaterLevel(entity_pos_t UNUSED(x), entity_pos_t UNUSED(z)) const + { + return entity_pos_t::FromInt(0); + } + + virtual float GetExactWaterLevel(float UNUSED(x), float UNUSED(z)) const + { + return 0.f; + } + + virtual void RecomputeWaterData() + { + } + + virtual void SetWaterLevel(entity_pos_t UNUSED(h)) + { + } +}; + +class MockFullTerrain : public ICmpTerrain +{ +private: + CTerrain* m_Terrain; +public: + virtual int GetComponentTypeId() const + { + return -1; + } + + static void ClassInit(CComponentManager& UNUSED(componentManager)) + { + } + + virtual bool IsLoaded() const + { + return m_Terrain->GetVerticesPerSide() != 0; + } + + virtual void Init(const CParamNode& UNUSED(paramNode)) + { + } + + virtual void Deinit() + { + m_Terrain = nullptr; + } + + virtual void Serialize(ISerializer& UNUSED(serialize)) + { + + } + + virtual void Deserialize(const CParamNode& paramNode, IDeserializer& UNUSED(deserialize)) + { + Init(paramNode); + } + + virtual CFixedVector3D CalcNormal(entity_pos_t x, entity_pos_t z) const + { + CFixedVector3D normal; + m_Terrain->CalcNormalFixed((x / static_cast(TERRAIN_TILE_SIZE)).ToInt_RoundToZero(), (z / static_cast(TERRAIN_TILE_SIZE)).ToInt_RoundToZero(), normal); + return normal; + } + + virtual CVector3D CalcExactNormal(float x, float z) const + { + return m_Terrain->CalcExactNormal(x, z); + } + + virtual entity_pos_t GetGroundLevel(entity_pos_t x, entity_pos_t z) const + { + return m_Terrain->GetExactGroundLevelFixed(x, z); + } + + virtual float GetExactGroundLevel(float x, float z) const + { + return m_Terrain->GetExactGroundLevel(x, z); + } + + virtual u16 GetTilesPerSide() const + { + ssize_t tiles = m_Terrain->GetTilesPerSide(); + + if (tiles == -1) + return 0; + ENSURE(1 <= tiles && tiles <= 65535); + return (u16)tiles; + } + + virtual u32 GetMapSize() const + { + return GetTilesPerSide() * TERRAIN_TILE_SIZE; + } + + virtual u16 GetVerticesPerSide() const + { + ssize_t vertices = m_Terrain->GetVerticesPerSide(); + ENSURE(1 <= vertices && vertices <= 65535); + return (u16)vertices; + } + + virtual CTerrain* GetCTerrain() + { + return m_Terrain; + } + + virtual void SetTerrain(CTerrain* t) + { + m_Terrain = t; + } + + virtual void MakeDirty(i32 i0, i32 j0, i32 i1, i32 j1) + { + CMessageTerrainChanged msg(i0, j0, i1, j1); + GetSimContext().GetComponentManager().BroadcastMessage(msg); + } + + virtual void ReloadTerrain(bool UNUSED(ReloadWater)) + { + u16 tiles = GetTilesPerSide(); + u16 vertices = GetVerticesPerSide(); + + CmpPtr cmpObstructionManager(GetSystemEntity()); + if (cmpObstructionManager) + { + cmpObstructionManager->SetBounds(entity_pos_t::Zero(), entity_pos_t::Zero(), + entity_pos_t::FromInt(tiles * static_cast(TERRAIN_TILE_SIZE)), + entity_pos_t::FromInt(tiles * static_cast(TERRAIN_TILE_SIZE))); + } + + CmpPtr cmpRangeManager(GetSystemEntity()); + if (cmpRangeManager) + { + cmpRangeManager->SetBounds(entity_pos_t::Zero(), entity_pos_t::Zero(), + entity_pos_t::FromInt(tiles * static_cast(TERRAIN_TILE_SIZE)), + entity_pos_t::FromInt(tiles * static_cast(TERRAIN_TILE_SIZE)), + vertices); + } + MakeDirty(0, 0, tiles + 1, tiles + 1); + } +}; + +class MockFootprint : public ICmpFootprint +{ + private: + entity_pos_t m_Height; + public: + + virtual int GetComponentTypeId() const { return IID_Footprint; } + virtual void Init(const CParamNode& UNUSED(paramNode)) { } + virtual void Deinit() {} + virtual void Serialize(ISerializer& UNUSED(serialize)) { } + virtual void Deserialize(const CParamNode& paramNode, IDeserializer& UNUSED(deserialize)) + { Init(paramNode); } + virtual void GetShape(EShape& UNUSED(shape), entity_pos_t& UNUSED(size0), entity_pos_t& UNUSED(size1), entity_pos_t& height) const + { + height = m_Height; + } + virtual entity_pos_t GetHeight() const + { + return m_Height; + } + virtual void SetHeight(entity_pos_t h) + { + m_Height = h; + } + virtual CFixedVector3D PickSpawnPoint(entity_id_t UNUSED(spawned)) const + { + return CFixedVector3D(); + } + virtual CFixedVector3D PickSpawnPointBothPass(entity_id_t UNUSED(spawned)) const + { + return CFixedVector3D(); + } +}; + +#include class TestCmpRangeManager : public CxxTest::TestSuite { public: @@ -82,21 +301,252 @@ CXeromyces::Terminate(); } + void test_losComputation() + { + ComponentTestHelper test(g_ScriptRuntime); + + ICmpRangeManager* cmp = test.Add(CID_RangeManager, "", SYSTEM_ENTITY); + + entity_id_t entityId = 100; + int playerId = 1; + int playerId2 = 2; + + MockVision vision; + vision.SetRange(entity_pos_t::FromInt(64)); + test.AddMock(entityId, IID_Vision, vision); + + MockPosition position; + test.AddMock(entityId, IID_Position, position); + + MockFootprint footprint; + footprint.SetHeight(entity_pos_t::FromInt(5)); + test.AddMock(entityId, IID_Footprint, footprint); + + CTerrain mTerrain; + MockFullTerrain terrain; + terrain.SetTerrain(&mTerrain); + // Flat terrain + mTerrain.Initialize(8, nullptr); + + MockWater water; + test.AddMock(SYSTEM_ENTITY, IID_WaterManager, water); + + int xMax = 512; + ssize_t tvps = xMax / TERRAIN_TILE_SIZE + 1; + + cmp->SetBounds(entity_pos_t::FromInt(0), entity_pos_t::FromInt(0), entity_pos_t::FromInt(xMax), entity_pos_t::FromInt(xMax), tvps); + + // Check that nothing is explored + TS_ASSERT_EQUALS(cmp->GetPercentMapExplored(playerId), 0); + + { CMessageCreate msg(entityId); cmp->HandleMessage(msg, false); } + { CMessageOwnershipChanged msg(entityId, -1, playerId); cmp->HandleMessage(msg, false); } + { CMessagePositionChanged msg(entityId, true, entity_pos_t::FromInt(247), entity_pos_t::FromDouble(257.95), entity_angle_t::Zero()); cmp->HandleMessage(msg, false); } + + // Check that something is explored for player1 + u8 expl = cmp->GetPercentMapExplored(playerId); + TS_ASSERT_LESS_THAN(0, expl); + // And the same amount is visible for player1 and nothing explored or visible for player2 + u32 vis = 0; + u32 ee = 0; + for (int i = 0; i < tvps; ++i) { + for (int j = 0; j < tvps; ++j) { + if (cmp->TestVisibility(i, j, playerId, ICmpRangeManager::LOS_VISIBLE)) + vis = vis + 1; + if (cmp->TestVisibility(i, j, playerId, ICmpRangeManager::LOS_EXPLORED)) + ee = ee + 1; + TS_ASSERT_EQUALS(cmp->TestVisibility(i, j, playerId2, ICmpRangeManager::LOS_VISIBLE), false); + TS_ASSERT_EQUALS(cmp->TestVisibility(i, j, playerId2, ICmpRangeManager::LOS_EXPLORED), false); + } + } + TS_ASSERT_LESS_THAN(0, ee); + TS_ASSERT_LESS_THAN(0, vis); + u32 explV = cmp->GetExploredVertices(playerId); + // Explored vertices matches count of explored vertices in map + TS_ASSERT_EQUALS(ee, explV); + // The same amount is explored and visible + TS_ASSERT_EQUALS(ee, vis); + + { CMessageOwnershipChanged msg(entityId, playerId, -1); cmp->HandleMessage(msg, false); } + { CMessageDestroy msg(entityId); cmp->HandleMessage(msg, false); } + + // Check that nothing is visible + u32 ee2 = 0; + for (int i = 0; i < tvps; ++i) + for (int j = 0; j < tvps; ++j) { + TS_ASSERT_EQUALS(cmp->TestVisibility(i, j, playerId, ICmpRangeManager::LOS_VISIBLE), false); + if (cmp->TestVisibility(i, j, playerId, ICmpRangeManager::LOS_EXPLORED)) + ee2 = ee2 + 1; + } + // And still the same amount is explored as before + TS_ASSERT_EQUALS(ee, ee2); + + } + + void test_visibility() + { + ComponentTestHelper test(g_ScriptRuntime); + + ICmpRangeManager* cmp = test.Add(CID_RangeManager, "", SYSTEM_ENTITY); + + entity_id_t entityId = 100; + entity_id_t entityId2 = 200; + player_id_t playerId = 1; + player_id_t playerId2 = 2; + + // Setup entity 1 + int numInt1 = IID__LastNative; + MockVision vision1; + vision1.SetRange(entity_pos_t::FromInt(10)); + test.AddMock(entityId, IID_Vision, vision1); + + MockPosition position1; + test.AddMock(entityId, IID_Position, position1); + + MockFootprint footprint1; + footprint1.SetHeight(entity_pos_t::FromInt(5)); + test.AddMock(entityId, IID_Footprint, footprint1); + + MockOwnership ownership1; + ownership1.SetOwner(playerId); + test.AddMock(entityId, IID_Ownership, ownership1); + + SEntityComponentCache* compCache1 = (SEntityComponentCache*)calloc(1, + sizeof(SEntityComponentCache) + sizeof(IComponent*) * numInt1); + ENSURE(compCache1 != nullptr); + compCache1->numInterfaces = numInt1 + 1; + compCache1->interfaces[IID_Position] = &position1; + compCache1->interfaces[IID_Ownership] = &ownership1; + compCache1->interfaces[IID_Footprint] = &footprint1; + compCache1->interfaces[IID_Vision] = &vision1; + CEntityHandle handle1(entityId, compCache1); + + // Setup entity 2 + MockVision vision2; + vision2.SetRange(entity_pos_t::FromInt(20)); + test.AddMock(entityId2, IID_Vision, vision2); + + MockPosition position2; + test.AddMock(entityId2, IID_Position, position2); + + MockFootprint footprint2; + footprint2.SetHeight(entity_pos_t::FromInt(5)); + test.AddMock(entityId2, IID_Footprint, footprint2); + + MockOwnership ownership2; + ownership2.SetOwner(playerId2); + test.AddMock(entityId2, IID_Ownership, ownership2); + + SEntityComponentCache* compCache2 = (SEntityComponentCache*)calloc(1, + sizeof(SEntityComponentCache) + sizeof(IComponent*) * numInt1); + ENSURE(compCache2 != nullptr); + compCache2->numInterfaces = numInt1 + 1; + compCache2->interfaces[IID_Position] = &position2; + compCache2->interfaces[IID_Ownership] = &ownership2; + compCache2->interfaces[IID_Footprint] = &footprint2; + compCache2->interfaces[IID_Vision] = &vision2; + CEntityHandle handle2(entityId2, compCache2); + + // Setup players + std::vector see1; + see1.push_back(playerId); + std::vector see2; + see2.push_back(playerId2); + + CTerrain mTerrain; + MockFullTerrain terrain; + terrain.SetTerrain(&mTerrain); + // Flat terrain + mTerrain.Initialize(8, nullptr); + + MockWater water; + test.AddMock(SYSTEM_ENTITY, IID_WaterManager, water); + + int xMax = 512; + ssize_t tvps = xMax / TERRAIN_TILE_SIZE + 1; + + cmp->SetSharedLos(playerId, see1); + TS_ASSERT_EQUALS(cmp->GetSharedLosMask(playerId), ICmpRangeManager::LOS_MASK << (2 * (playerId - 1))); + cmp->SetSharedLos(playerId2, see2); + cmp->SetBounds(entity_pos_t::FromInt(0), entity_pos_t::FromInt(0), entity_pos_t::FromInt(xMax), entity_pos_t::FromInt(xMax), tvps); + + { CMessageCreate msg(entityId); cmp->HandleMessage(msg, false); } + { CMessageCreate msg(entityId2); cmp->HandleMessage(msg, false); } + + { CMessageOwnershipChanged msg(entityId, -1, playerId); cmp->HandleMessage(msg, false); } + { CMessageOwnershipChanged msg(entityId2, -1, playerId2); cmp->HandleMessage(msg, false); } + + position1.SetPosition(entity_pos_t::FromInt(100), entity_pos_t::FromDouble(100)); + position2.SetPosition(entity_pos_t::FromInt(115), entity_pos_t::FromDouble(100)); + + { CMessagePositionChanged msg(entityId, true, entity_pos_t::FromInt(100), entity_pos_t::FromDouble(100), entity_angle_t::Zero()); cmp->HandleMessage(msg, false); } + { CMessagePositionChanged msg(entityId2, true, entity_pos_t::FromInt(115), entity_pos_t::FromDouble(100), entity_angle_t::Zero()); cmp->HandleMessage(msg, false); } + CmpPtr cmpPosition(handle1); + if (!cmpPosition) + TS_FAIL("entity with handle1 has not position component"); + CFixedVector2D pos = cmpPosition->GetPosition2D(); + int i = (pos.X / static_cast(TERRAIN_TILE_SIZE)).ToInt_RoundToNearest(); + int j = (pos.Y / static_cast(TERRAIN_TILE_SIZE)).ToInt_RoundToNearest(); + if (!cmp->TestVisibility(i, j, playerId, ICmpRangeManager::LOS_VISIBLE)) + TS_FAIL("Entity does not see its own position"); + + // Players see their own entities + TS_ASSERT_EQUALS(cmp->GetLosVisibility(handle1, playerId), ICmpRangeManager::VIS_VISIBLE); + TS_ASSERT_EQUALS(cmp->GetLosVisibility(handle2, playerId2), ICmpRangeManager::VIS_VISIBLE); + // Player1 cannot see entity2 + TS_ASSERT_EQUALS(cmp->GetLosVisibility(handle2, playerId), ICmpRangeManager::VIS_HIDDEN); + // Player2 can see entity1 + TS_ASSERT_EQUALS(cmp->GetLosVisibility(handle1, playerId2), ICmpRangeManager::VIS_VISIBLE); + + position2.SetPosition(entity_pos_t::FromInt(121), entity_pos_t::FromDouble(100)); + { CMessagePositionChanged msg(entityId2, true, entity_pos_t::FromInt(121), entity_pos_t::FromDouble(100), entity_angle_t::Zero()); cmp->HandleMessage(msg, false); } + // Player2 cannot see entity1 + TS_ASSERT_EQUALS(cmp->GetLosVisibility(handle1, playerId2), ICmpRangeManager::VIS_HIDDEN); + + position1.SetPosition(entity_pos_t::FromInt(118), entity_pos_t::FromDouble(100)); + { CMessagePositionChanged msg(entityId, true, entity_pos_t::FromInt(118), entity_pos_t::FromDouble(100), entity_angle_t::Zero()); cmp->HandleMessage(msg, false); } + // Both players can see both entities + TS_ASSERT_EQUALS(cmp->GetLosVisibility(handle1, playerId2), ICmpRangeManager::VIS_VISIBLE); + TS_ASSERT_EQUALS(cmp->GetLosVisibility(handle2, playerId), ICmpRangeManager::VIS_VISIBLE); + } + // TODO It would be nice to call Verify() with the shore revealing system // but that means testing on an actual map, with water and land. void test_basic() { + ComponentTestHelper test(g_ScriptRuntime); ICmpRangeManager* cmp = test.Add(CID_RangeManager, "", SYSTEM_ENTITY); MockVision vision; + vision.SetRange(entity_pos_t::FromInt(64)); test.AddMock(100, IID_Vision, vision); MockPosition position; test.AddMock(100, IID_Position, position); + MockFootprint footprint; + footprint.SetHeight(entity_pos_t::FromInt(5)); + test.AddMock(100, IID_Footprint, footprint); + + CTerrain mTerrain; + MockFullTerrain terrain; + terrain.SetTerrain(&mTerrain); + // Flat terrain + mTerrain.Initialize(8, nullptr); + if (mTerrain.GetVertexGroundLevel(61, 64) > 0) + TS_FAIL("terrain get vertex ground level"); + test.AddMock(SYSTEM_ENTITY, IID_Terrain, terrain); + terrain.Init(CParamNode()); + + if (!terrain.GetCTerrain()) + TS_FAIL("GetCTerrain returns null"); + + MockWater water; + test.AddMock(SYSTEM_ENTITY, IID_WaterManager, water); + // This tests that the incremental computation produces the correct result // in various edge cases @@ -152,5 +602,7 @@ previousOwner = newOwner; } } + + terrain.Deinit(); } };