aliens

Show Posts

This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.


Topics - djemon_lda

Pages: [1]
1
Troubleshooting / kneeling bug
« on: October 19, 2013, 04:46:04 pm »
I've seen somewhere in the code that you are preventing flying soldiers from kneeing and I think I've found a bug.

steps:
1. get on a mission with guys with fying suit
2. order the soldier to fly out the avenger
3:
a) use the elevate down button
b) order soldier to "walk" to the voxel directly below him, so that he stands on ground
4. hit the knee button
current result:
a) the soldier doesn't do anything.
b) the soldier knees for one state machine update loop and stands up without command ( after that he can kneel normally )

what I think is the expected result:
the soldier should end up on his knee.

2
Suggestions / testing the product on dev side
« on: October 17, 2013, 03:12:13 pm »
hey guys, have you ever considered using testing the code ? there is a neat thing called gtest and gmock made by google, that helps making tests and mocking classes. I can configure it for visual studio for you. there is a nice tutorial on how to make tests with this, called gtest cookbook or something like that - online and free.

this would enable you to test a lot of things before it gets to the users. for example you can make multiple scenarios checking things like:

1. all units with higher reaction than the walker/shooter are in the reactionist list
2. all units from reactionist list that can shoot, will do so
3. if an better scored reactionist can't shoot, he will not prevent other reactionists from shooting

and so on.

this also boosts the development speed.

basically everything can be tested like this, and this is also an indication of where you need modiffications in your architecture.

3
Programming / code review #1
« on: October 13, 2013, 03:18:49 pm »
ok, so yesterday in EU4 I've got a little too greedy, kicked the shit out of a neighbour country and its allies, and took a little too much from their countries ( including vasalizing one of them by force, and taking a bit land from another ) so they made a coalition against me, and to regenerate before yet another war I turned off the game and thought I need to relax in a different way.

I'm aiming in fixing the reaction fire mechanics, so I wanted to use a priority queue, but then I thought that the regular priority que doesn't my full needs in my project, so it is likely it wouldn't fit yours here, hence I've got a fun attitude of making a nice heap that would meet most of my needs ( I still will need to expand it a little for my project ) and sharing it.

I've used __forceinline when I wanted to be totally sure the compiler will inline the code. I also tried to bring things up if possible, so that is why I've made static all the metods that don't use a field, or a nonstatic method, because not passing the "this" pointer saves time. That way I got both : speed as if all that was typed directly in the code, and readability - and thanks to this I could do things like bitwise shifts, instead of multiplying/dividing by 2, because things like that are hidden behind meaningful names that describe my intentions.

The reason why I did this in 3 ways ( defined a method outside the class, defined it inside the class, defined inside and use __forceinline ) is because I wanted respectively: to be sure that the compiler will generate a function call, to suggest that a method can be inlined if the compiler sees this as an optimization, to make sure, that the piece of code will be inlined.

I know you are compiling on different platforms, so this should do the trick :)

Code: [Select]
#ifdef _MSC_VER
#define __forceinline __forceinline
#else
#define __forceinline inline
#endif

so here it is:


Code: [Select]
template<
typename DataType,
typename HeapIndexer = DirectIndexer,
typename HeapRelation = std::greater_equal<DataType>,
template <typename> class IndexParameterDefinition = PassByValue,
template <typename> class DataParameterDefinition = PassByValue
>
class Heap
{
private:
static const size_t TopIndex = 1;
public:
typedef typename IndexParameterDefinition<typename HeapIndexer::IndexingType>::PassedValue Index;
typedef typename DataParameterDefinition<DataType>::PassedValue Data;
Heap(const std::vector<DataType> data);

__forceinline const size_t& Size()const
{
return _heapSize;
}

const DataType& operator[](const Index indexToBrowseWith)const;

const DataType& Top()const
{
return _heapData[TopIndex];
}
void SetValue(const Index index, Data dataType);
__forceinline void Pop()
{
RemoveInternal(TopIndex);
HeapDown(TopIndex);
}
void Remove(const Index index)
{
const size_t indexToRemoveAt = _indexer.ToRawIndex(index);
RemoveInternal(indexToRemoveAt);
HeapifyInternal(indexToRemoveAt);
}
const bool IsEmpty()const
{
return _heapSize == 0;
}
void Clear();
private:

void HeapifyInternal(const size_t index);
void HeapDown(const size_t index);
size_t GetIndexOfHighestInTercet(const size_t index)const;
void HeapUp(const size_t index);
void Swap(const size_t leftIndex, const size_t rightIndex);
void SetMockOnZeroIndex();
void RemoveInternal(const size_t index)
{
Swap(index, _heapSize);
_heapSize--;
}
bool ShouldLeftsideBeHigherInHeap(const size_t leftsideIndex, const size_t rightsideIndex)const
{
return _shouldLeftGoUp(_heapData[leftsideIndex],_heapData[rightsideIndex]);
}
bool NeedsUpHeaping(const size_t index)const
{
const size_t parent = GetParent(index);
https:// if index = 1, then parent will be equal to 0. this is the only situation where an index doesn't have a legal parent.
return parent && _shouldLeftGoUp(_heapData[index],_heapData[parent]);
}

__forceinline static size_t GetLeftChild(const size_t index)
{
return index << 1; https:// multiply by 2
}
__forceinline static size_t GetRightChild(const size_t index)
{
return GetLeftChild(index) + 1; https:// GetLeftChild(...) is forced inline, so no overhead.
}
__forceinline static size_t GetParent(const size_t index)
{
return index >> 1; https:// divide by 2
}


__forceinline bool IsValidChild(const size_t index)const
{
return index <= _heapSize;
}

https:// an assumption that allows the optimization:
https:// the index of the parent given to this method is always acquired
https:// by using the GetParent method on a legal index inside the
__forceinline static bool IsParentOnHeap(const size_t indexOfAParent)
{
https:// index is in range 0 to 2^32-1, so 'index' returns the same bool value as 'index>0'
return indexOfAParent;
}

std::vector<DataType> _heapData;
HeapIndexer _indexer;
HeapRelation _shouldLeftGoUp;
size_t _heapSize;
};

template<
typename DataType,
typename HeapIndexer,
typename HeapRelation,
template <typename> class IndexParameterDefinition,
template <typename> class DataParameterDefinition
>
const DataType& Heap<DataType, HeapIndexer, HeapRelation,IndexParameterDefinition,DataParameterDefinition>::operator[](const Index indexToBrowseWith)const
{
return _heapData[ _indexer.ToRawIndex(indexToBrowseWith) ];
}
template<
typename DataType,
typename HeapIndexer,
typename HeapRelation,
template <typename> class IndexParameterDefinition,
template <typename> class DataParameterDefinition
>
void Heap<DataType, HeapIndexer, HeapRelation,IndexParameterDefinition,DataParameterDefinition>::Swap(const size_t leftIndex, const size_t rightIndex)
{
std::swap(_heapData[leftIndex], _heapData[rightIndex]);
_indexer.Swap(leftIndex, rightIndex);
}
template<
typename DataType,
typename HeapIndexer,
typename HeapRelation,
template <typename> class IndexParameterDefinition,
template <typename> class DataParameterDefinition
>
void Heap<DataType, HeapIndexer, HeapRelation,IndexParameterDefinition,DataParameterDefinition>::HeapUp(const size_t index)
{
size_t reciever = GetParent(index);
size_t donor = index;
while(IsParentOnHeap(reciever) && ShouldLeftsideBeHigherInHeap(donor, reciever)) https:// a small optimization
{
Swap(reciever, donor);
donor = reciever;
reciever = GetParent(reciever);
}
}

template<
typename DataType,
typename HeapIndexer,
typename HeapRelation,
template <typename> class IndexParameterDefinition,
template <typename> class DataParameterDefinition
>
size_t Heap<DataType, HeapIndexer, HeapRelation,IndexParameterDefinition,DataParameterDefinition>::GetIndexOfHighestInTercet(const size_t index)const
{
size_t higherItemIndex = index;
const size_t leftChild = GetLeftChild(index);
const size_t rightChild = GetRightChild(index);
if(IsValidChild(leftChild) && ShouldLeftsideBeHigherInHeap(leftChild, higherItemIndex))
{
higherItemIndex = leftChild;
}
if(IsValidChild(rightChild) && ShouldLeftsideBeHigherInHeap(rightChild, higherItemIndex))
{
higherItemIndex = rightChild;
}
return higherItemIndex;
}

template<
typename DataType,
typename HeapIndexer,
typename HeapRelation,
template <typename> class IndexParameterDefinition,
template <typename> class DataParameterDefinition
>
void Heap<DataType, HeapIndexer, HeapRelation,IndexParameterDefinition,DataParameterDefinition>::HeapifyInternal(const size_t index)
{
if(NeedsUpHeaping(index))
{
HeapUp(index);
}else
{
HeapDown(index);
}
}

template<
typename DataType,
typename HeapIndexer,
typename HeapRelation,
template <typename> class IndexParameterDefinition,
template <typename> class DataParameterDefinition
>
void Heap<DataType, HeapIndexer, HeapRelation,IndexParameterDefinition,DataParameterDefinition>::HeapDown(const size_t index)
{
size_t donor = index;
size_t reciever = GetIndexOfHighestInTercet(donor);
while(donor != reciever)
{
Swap(donor,reciever);
donor = reciever;
reciever = GetIndexOfHighestInTercet(reciever);
}
}
template<
typename DataType,
typename HeapIndexer,
typename HeapRelation,
template <typename> class IndexParameterDefinition,
template <typename> class DataParameterDefinition
>
void Heap<DataType, HeapIndexer, HeapRelation,IndexParameterDefinition,DataParameterDefinition>::SetValue(const Index index, Data dataType)
{
const size_t internalIndex = _indexer.ToRawIndex(index);
_heapData[internalIndex] = dataType;
HeapifyInternal(internalIndex);
}
template<
typename DataType,
typename HeapIndexer,
typename HeapRelation,
template <typename> class IndexParameterDefinition,
template <typename> class DataParameterDefinition
>
Heap<DataType, HeapIndexer, HeapRelation,IndexParameterDefinition,DataParameterDefinition>::Heap(const std::vector<DataType> data)
: _heapSize(data.size())
{
https:// add 0 index mock value
SetMockOnZeroIndex();
for(auto currentDataItem = data.begin(); currentDataItem != data.end(); ++currentDataItem)
{
_heapData.push_back(*currentDataItem);
}
const size_t halfOfHeap = _heapSize / 2;
for(size_t currentIndex = halfOfHeap; currentIndex >= TopIndex; --currentIndex)
{
HeapDown(currentIndex);
}
}
template<
typename DataType,
typename HeapIndexer,
typename HeapRelation,
template <typename> class IndexParameterDefinition,
template <typename> class DataParameterDefinition
>
void Heap<DataType, HeapIndexer, HeapRelation,IndexParameterDefinition,DataParameterDefinition>::Clear()
{
_heapData.clear();
_heapSize = 0;
_indexer.Clear();
SetMockOnZeroIndex();

}

template<
typename DataType,
typename HeapIndexer,
typename HeapRelation,
template <typename> class IndexParameterDefinition,
template <typename> class DataParameterDefinition
>
void Heap<DataType, HeapIndexer, HeapRelation,IndexParameterDefinition,DataParameterDefinition>::SetMockOnZeroIndex()
{
_indexer.Add (Index(), 0);
_heapData.push_back(DataType());
}

I've wrote two simple heap indexers:
the default one, which allows direct indexing, and takes just one byte of memory :)
Code: [Select]
struct DirectIndexer
{
typedef size_t IndexingType;
__forceinline size_t ToRawIndex(const size_t& indirectIndex)const
{
return indirectIndex;
}
https:// no need to handle mapping in a direct indexer :)
https:// calls to those method should be removed from the binary when compiled with -o2
void Add(const size_t, const size_t){}
void Swap(const size_t, const size_t){}
void Clear(){}
};
a templated default mapped indexer ( for example to be able to map the things in the heap with strings, points or whatever you may wish ) - this one weights 40bytes
Code: [Select]
template<typename IndexType>
struct Indexer
{
typedef typename IndexType IndexingType;
__forceinline size_t ToRawIndex(const IndexType& indirectIndex)
{
return _indexToInternalMap[indirectIndex];
}
void Add(const IndexType& indirectIndex, const size_t directIndex)
{
_indexToInternalMap[indirectIndex] = directIndex;
_internalToIndexMap.push_back( indirectIndex );
}
void Swap(const size_t leftDirectIndex, const size_t rightDirectIndex)
{
const IndexType& leftIndirectIndex = _internalToIndexMap[leftDirectIndex];
const IndexType& rightIndirectIndex = _internalToIndexMap[rightDirectIndex];
std::swap(_internalToIndexMap[leftDirectIndex], _internalToIndexMap[rightDirectIndex]);
std::swap(_indexToInternalMap[leftIndirectIndex], _indexToInternalMap[rightIndirectIndex]);
}
void Clear()
{
_internalToIndexMap.clear();
_indexToInternalMap.clear();
}
private:
std::map<IndexType,size_t> _indexToInternalMap;
std::vector<IndexType> _internalToIndexMap;
};

I also have given an option to chose how to pass the parameters to the public methods, whether it would be by value or by reference, thanks to these two guys:
Code: [Select]
template<typename T>
struct PassByValue
{
typedef T PassedValue;
};
Code: [Select]
template<typename T>
struct PassByReference
{
typedef T& PassedValue;
};
finally, I've made simplified templates, because mostly the change will be between the type of data hold and the type of index, so I've made these four guys, all with default way of passing value to the public methods, and relation set accordingly to their names.

Code: [Select]
template<typename DataType>
class MaxHeap : public Heap<DataType>{};
Code: [Select]
template<typename DataType>
class MinHeap : public Heap<DataType,DirectIndexer,std::less_equal<DataType>>
{
public:
MinHeap(const std::vector<DataType> data) : Heap(data){}
};
Code: [Select]
template<typename DataType, typename IndexType>
class IndexedMaxHeap : public Heap<DataType, Indexer<IndexType>>{};
Code: [Select]
template<typename DataType, typename IndexType>
class IndexedMinHeap : public Heap<DataType, Indexer<IndexType>, std::less_equal<DataType>>{};


I've made a lot of automated, randomized tests ( I was hitting hard the part with removing items from an arbitrary index, and tested the mechanism above 500 milions of times on small and medium heap sizes ( <50, 10000 elements respectively ) and with bigger or smaller duplicate value ratio ( due to setting the value cap for 50 to 32 thousand ( the max rand value ) ), and in total there was above 1000000000 tests of all the heaps mechanisms in total).

the method I was checking the heap property preserved at all times is

Code: [Select]
template<typename T>
bool IsChildInRightRelationsWithParent(const T& child, const T& parent)
{
#ifdef _MIN_HEAP_
return child >= parent;
#else
return child <= parent;
#endif
}

template<typename T>
bool RecurrentCheck(const T& heap, const size_t index)
{
const size_t size = heap.Size();
const size_t leftChild = index * 2;
const size_t rightChild = leftChild + 1;

const bool hasLeftChild = leftChild <= size;
const bool hasRightChild = rightChild <= size;

const bool leftChildOK = (hasLeftChild && IsChildInRightRelationsWithParent(heap[leftChild] , heap[index])) || !hasLeftChild;
const bool rightChildOK = ((hasRightChild) && IsChildInRightRelationsWithParent(heap[rightChild] , heap[index])) || !hasRightChild;

const bool rightIsOk = (!hasRightChild) || RecurrentCheck(heap, rightChild);
const bool leftIsOk = (!hasLeftChild) || RecurrentCheck(heap, leftChild);
const bool isEverythingAllRight = leftChildOK && rightChildOK && leftIsOk && rightIsOk;
}

template<typename T>
bool CheckHeap(const T& heap)
{
return RecurrentCheck(heap, 1);
}

I've used a trick here, that allows to avoid branching of the recurrent function.

if something looks suspicious, or like na error, post about it, and I will verify and comment the reasonin behind.
regards,
djemon_lda

4
Troubleshooting / interesting bug in battlescape - load/save situation
« on: September 23, 2013, 10:13:08 pm »
ok, so here it is, done out of pure curiosity:

1. my soldier has gone berserk
2. I spammed the options tab, and clicked save while he was in this mode
3. I load the game, and the guy is all stuck with his gun pointed in the ether.

If I try to move him, he the game will hang, and will be have to killed with process manager.

I attach the save game.
EDIT:
if anyone gets to this, I have found a workaround: order the guy to shot in front of him. he will make a shot, take his weapon to 'stand by', and will be mobile again, and wont hang the game.

5
Troubleshooting / bug - using the "Sack" button on the soldiers view
« on: September 20, 2013, 09:13:44 pm »
SupSuper, you've said you're the geoscape developer, so here is something for you.

When you go base->soldiers and pick a soldier, then you can sack him using the Sack button in the upper right corner.

If your currently viewed soldier is the last one on the list and you click the sack button, the first solider on the list gets deleted as well.

6
Programming / A bug in battlescape and a fix for it
« on: September 20, 2013, 02:22:03 am »
Hello again! :)

SupSuper or Warboy, could you please take a look on that?

I remember that I've read hear on the forum, that there is no reason to try and load the state of the battlescape and try to save units, because you save the seed. I've taken a look into the code, because I was wandering what random generator are you using ( would it be a mersenne twister, or some simple noncryptographic randomizer ) and found out that you are using a global seed (at least for the battlescape). I immedieately have found a way to trick your anti cheating security done with saving the seed.

Scenario 1:
1) alien, and two of my soldiers see it, my turn
2) I save the game.
3) I shot with guy1. I miss. Alien retaliates. My guy dies.
4) I load. I shot with guy1. I miss. Alien retaliates. My guy dies.
5) I load. I take guy3, that is somewhere far away. I shot a random wall.
6) I shot with guy1. I miss. Alien retaliates. ALIEN MISSSES

Why this happens in detail?
1) Lets say my seed is A, and because of that the sequence of numbers generated is B,C,D,E,F,G,...
2) You have saved a global seed, so no matter who uses the random number, the sequence goes forward.
3) in scenario 1, right after I save the game, guy1 gets value B from the RNG and he misses. Alien gets value C, and hits.
then I load the game, so the seed is again A, guy1 gets value B from the RNG and he misses (again) and the alien gets C, so he hits.
then I load the game, so the seed is again A, guy3 shoots the wall getting B from RNG, guy1 gets C and he misses, but alien gets D (no juvenile humor here!) and misses.

I have came up with multiple scenarios of this, and the only way to handle this properly is to keep an instance of a random number generator in each of the battle units.

Let's take the same scenario, with a random number generator instance per a battle unit, shall we?

alien has seed A, guy1 has seed G and guy3 has seed M.

Scenario 1 with an instance of a random generator per a battle unit.
1) alien, and two of my soldiers see it, my turn
2) I save the game. ( with all the different seeds for each unit )
3) I shot with guy1(he has A, so his generator generates B). I miss. Alien retaliates (it has seed G, so he gets number H, and hits). My guy dies.
4) I load. I shot with guy1(he has A, so his generator generates B). I miss. Alien retaliates (it has seed G, so he gets number H, and hits). My guy dies.
5) I load. I take guy3, that is somewhere far away. I shot a random wall(he has seed M, hence getting number N and not changing the next value that the alien and guy1 will get).
6) I shot with guy1(I loaded, so his seed is A, and he gets B from RNG, because he has his own seed). I miss. Alien retaliates(he has his own seed G so he gets H again and hits! :) ). my guy dies

a lazy fix would just be to have an int in each battle unit named _seed and get his test values by a method like:
Code: [Select]
int BattleUnit::GenerateOwnRandomNumber()const
{
srand(_seed);
_seed = rand();
return _seed;
}
but I would advise using an object, because this method is "a bit" slow. You can try something from <random> header (c++11), or if you wait a day or two I will get you a nice, and small piece of code ( compact in size and fast ) random generator, that isn't cryptographic, but had nice results... I just need to find that implementation on my email :)

Regards,
djemon_lda

7
Suggestions / a thought from a c++ software developper
« on: September 16, 2013, 02:04:08 am »
Hello forum users, and openXcom developpers. I have been very enthusiastic once I have read about the openXcom project by some wierd coincidence. UFO:Enemy Unknown was undeniably the game of my life. It was extremelly playable, even more than later encountered dune2:battle for arrakis, or starcraft:broodwar years after. It was the very same thing this time - nothing changed. I have installed it somewhere around midnight, and stopped playing just before 6A.M. having full tech and a lot of talented psionics, basically only waiting for the right moment to invade cydonia...

With the same dose of fanatism I have helplessly fallen under the might of the thought to help your development team with maintaining the product, fixing its problems and delivering new, configurable functionality. All that until I've taken a look on your codebase.

I personally think your project could use some help of a system architect. I won't name what I've seen until you decide whether you want some help on the game's architecture or not, but some simple refactoring would facilitate further development and made the code a lot more readible and flexible, giving you productivity and a greater scope of changes you can incorporate to satisfy your audience, alongside with less errors introduced.

It's your call - I will check this forum from time to time for an answer from the dev.

Regards,

Pages: [1]