Skip to main content

News

Topic: Sphere SFML v0.90 (Read 107258 times) previous topic - next topic

0 Members and 5 Guests are viewing this topic.
  • Radnen
  • [*][*][*][*][*]
  • Senior Staff
  • Wise Warrior
Re: Sphere SFML v0.75alpha
Reply #180
New Feature: Heap
So, in this engine I exposed a new feature, the heap data structure. I wrote a C# and JS version of one based on this exclent article: http://eloquentjavascript.net/appendix2.html

I find that while the Jurassic-compiled JS version of the heap is pretty fast, the C# variant-exposed-through-code version is much, much faster. So much so it can make a JS-based A* algorithm right at the speed I like: milliseconds. Of course, going further, I could continue to implement the A* pathfinder straight in C#, but a binary heap is still useful for many things, such as figuring out the next bullet to impact a target, efficiently find the next turn in a turn based combat system prioritized on speeds (example below), sort a list, find a closest enemy or ally, get a shortest distance, etc.

Example:
Code: (javascript) [Select]

var heap = new BinaryHeap(function(x) { return x.speed; });
heap.add({speed: 5});
heap.add({speed: 4});
heap.add({speed: 5});
heap.add({speed: 3});
heap.add({speed: 1});
heap.add({speed: 6});
heap.add({speed: 2});

heap.shift(); // get next fastest enemy

// or just get the sorted list:
var array = heap.toArray();

// underlying data changed dynamically? No problem, we can do a heapsort on it:
heap.resort();


What do you think about the API?
Code: (javascript) [Select]

heap.add(object); // adds and sorts in the object
heap.shift(); // returns the topmost priority item
heap.pop(); // removes the bottommost priority
heap.remove(node); // removes that node/item from the heap
heap.resort(); // resort the list (ideally for lists of objects)
heap.toArray(); // get underlying array
heap.size(); // get length of heap
heap.clear(); // clear out the heap


If I'm missing anything or it needs changes, feel free to ask.

Benchmarks:
JS A* algorithm on a worst-case 64*64 sized map with various heap implementations and Sphere engines.

SSFML using C# heap: 33ms
SSFML using JS heap: 100ms
Sphere 1.6 using JS heap: 80ms
Sphere 1.5 using JS heap: 140ms

Notice the SSFML version does not optimize the JS heap very well; it performs worse than Sphere 1.6 which is shocking! So in fact using the JS heap in 1.6 and checking for existence of native heap for SSFML will give you a good solution that is cross engine.
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

  • Fat Cerberus
  • [*][*][*][*][*]
  • Global Moderator
  • Sphere Developer
Re: Sphere SFML v0.75alpha
Reply #181
What exactly is a heap?  I've heard the term tons of times and I think I even looked it up once, but unfortunately I programmed in C/C++ for so long that I'm conditioned to automatically associate the term with the heap (i.e. free memory), which despite the fact I know is something entirely different, that particular meaning is so ingrained in my mind that the other meanings never seem to stick...
neoSphere 5.9.2 - neoSphere engine - Cell compiler - SSj debugger
forum thread | on GitHub

  • Radnen
  • [*][*][*][*][*]
  • Senior Staff
  • Wise Warrior
Re: Sphere SFML v0.75alpha
Reply #182
I'm pretty certain if you read the article, you'll learn exactly what a heap is. Fun fact: it is very similar to a binary tree, but faster due to efficient array lookups.
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

  • Fat Cerberus
  • [*][*][*][*][*]
  • Global Moderator
  • Sphere Developer
Re: Sphere SFML v0.75alpha
Reply #183
See, if I read the article I'm pretty sure it's not going to stick due to the other meaning being so deeply ingrained.  I figured if I had someone explain it to me (i.e. in a non-academic context) I'd be more likely to remember it.

Maybe I'm just weird.  :D
neoSphere 5.9.2 - neoSphere engine - Cell compiler - SSj debugger
forum thread | on GitHub

  • Radnen
  • [*][*][*][*][*]
  • Senior Staff
  • Wise Warrior
Re: Sphere SFML v0.75alpha
Reply #184
Do you know what a Binary Tree is? Do you know what Binary Search is? Because it's exactly that in array form.

Basically in a tree you have a node at index i, and then the indices at i*2 and i*2+1, would be it's children (the nodes right underneath it). So by using those formulas we can create a direct representation of a tree inside of an array. The benefit is that there is no stack recursion over node objects, and instead everything is reduced to efficient array accesses. The speeds arrive at O(Log2(N)) time (logarithmic time means it gets faster at finding the answer the more items there are with respect to linear time). It's nice in C#-land since I can type the underlying array, whereas in JS-land I can't.

I might add a BinaryTree next, but with the heap as fast as it is, I don't think it's wise. ;) You don't have to know how it works (on the inside) to use it in a game, though. Just know it orders inputs from smallest to largest really fast. Which is good for all the cases I pointed out a couple posts up.
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

  • Fat Cerberus
  • [*][*][*][*][*]
  • Global Moderator
  • Sphere Developer
Re: Sphere SFML v0.75alpha
Reply #185
Ah, that's pretty clever.  So basically the idea is that you take the tree (which is two-dimensional) and flatten it, then just index the flat array.  Neat, I never would have thought of something like that.  Not sure where the auto-sorting comes into play though, since nothing in your description of the actual tree structure indicated that the nodes had to be sorted. Am I missing something here?
neoSphere 5.9.2 - neoSphere engine - Cell compiler - SSj debugger
forum thread | on GitHub

  • N E O
  • [*][*][*][*][*]
  • Administrator
  • Senior Administrator
Re: Sphere SFML v0.75alpha
Reply #186
The auto-sort in a binary heap is almost always done upon insertion and insertion is usually O(2*log(N)) in worst case IIRC. The inserted node is compared to the current (root at the start) node and if less than it goes to the left child node else it goes to the right; that left or right node is then the current node. It usually repeats in that manner until either there are no more child nodes to compare to. The re-sort usually performs node "rotations" to re-balance the tree so search and future insertions are faster (the "bubbleUp" and "sinkDown" functions in the linked page).
  • Last Edit: December 26, 2013, 07:05:03 pm by N E O

Re: Sphere SFML v0.75alpha
Reply #187
Can we see the test code for the A*?

Have you tried using Typed Arrays for the A*? They are used for storing, accessing, and modifying binary data with very little overhead, and I've heard they are very fast.

I mean, Sphere 1.5-6 can't do it, but I would imagine Jurassic could, and I know V8 and modern SpiderMonkey can.

  • Radnen
  • [*][*][*][*][*]
  • Senior Staff
  • Wise Warrior
Re: Sphere SFML v0.75alpha
Reply #188
It has been proposed to ECMA: http://wiki.ecmascript.org/doku.php?id=strawman:typed_arrays

But, since the proposal is newer than 2010, it hadn't made it into ECMA v5, which is used by Jurassic. So it doesn't work. :( V8 has it since the internet is kinda their motivation. :P It looks good for being in ECMA 6 though. I can, however, implement the API in my engine, it shouldn't be too hard, and would make reading Sphere binary files like map, tileset, and spritests easier to read in (with JS, that is).

Edit:
Actually, I can't modify Jurassic to do that. I would need access to the [] operator (not the C# overload, but the JS one), which means adding to and modifying the parser so that a new Array type, the TypedArray, has the ability to get and set bits of an underlying buffer with the [] operator.

Because doing this in JS, is not possible:
Code: (javascript) [Select]

var buffer = new ArrayBuffer(100); // 00000000 ... 0000

var intarray = new Int32Array(buffer);
intarray[0] = 5;

buffer.toBinary() != 00000000 ... 0101

// there would need to be:
buffer.update(intarray); // but this is not a spec.


(Which is probably another reason why it is not standard).

Anyways, I'll attach the A* code. Put both into a test game folder, and try it out, using pathtest as the parent script. Use the left mouse button to create obstructions. F1 ... F6 loads maps, Shift + F1 ... F6 saves maps (for fun, testing etc), then use the right mouse button to set the two pathing nodes (you have to click a place for each node before it paves again). It is quite robust. It has 6 presets, three for speed (so you might not get shortest path, but a fast performance), and 3 accurate ones (shortest path, but slow). I'd use the first 3 for movement depending on how you want movement to work in your game (diagonal vs. tiled), and the bottom 3 for... academics. :P

The A* algorithm under the newer speed model, has these speeds in the Sphere Engines: (64*64 worst case)

SSFML: 36ms          - old: 33
Sphere 1.6: 67ms   - old: 80
Sphere 1.5: 104ms - old: 140

So, these are faster than earlier indeed, it might seem slower (36 v 33), but I found a worse worst case: not finding it's target. xD
  • Last Edit: December 27, 2013, 08:36:02 pm by Radnen
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

  • Radnen
  • [*][*][*][*][*]
  • Senior Staff
  • Wise Warrior
Re: Sphere SFML v0.75alpha
Reply #189
New Feature: XML serialization (alpha)

The idea is to have a different way to store data, we have:

1. The Sphere like ini-file format
2. JSON in a raw file.
3. ... and now XML!

Example:
Code: (javascript) [Select]

var file = new XmlFile("test.xml");
file.write("my_object", { x: 45, y: 54, ended: false, map: { name: "test.rmp", start: { x: 50, y: 50 } }, arr: [0, 1, 2] });
file.close();


Output:
Code: (xml) [Select]

<?xml version="1.0"?>
<!--Generated by Sphere SFML XML Content Serializer v1.0-->
<my_object s_x="45" s_y="54" s_ended="False">
  <o_map s_name="test.rmp">
    <o_start s_x="50" s_y="50" />
  </o_map>
  <a_arr s_0="0" s_1="1" s_2="2" />
</my_object>


Notice o_ means object, a_ array, s_ string, n_ number, b_ boolean, and I don't store functions.

The ultimate goal is to make data serialization easier than using JSON. Compare the above with this:
Code: (javascript) [Select]

var file = OpenRawFile();
var json = JSON.stringify({ x: 45, y: 54, ended: false, map: { name: "test.rmp", start: { x: 50, y: 50 } }, arr: [0, 1, 2] });
file.write(CreateByteArrayFromString(json));
file.flush();
file.close();


Which is not bad, but not easy to read for filesaving purposes. XML I think is a cleaner, more user friendly way (and the output is also human readable and therefore easier to spot issues in the saving).

The proposed API
Code: (javascript) [Select]

var file = new XmlFile();
file.write(name, object);
var o = file.read(name);
file.close();


I wanted it to be simple to use and store any kind of object datatype.
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

  • N E O
  • [*][*][*][*][*]
  • Administrator
  • Senior Administrator
Re: Sphere SFML v0.75alpha
Reply #190
I've always been partial to declaring a variable's type (object, array, string, etc) in XML as an attribute of the element, with my alternative method being <type name="x">value</type> or <bool name="isDone" value="true" />.

  • Radnen
  • [*][*][*][*][*]
  • Senior Staff
  • Wise Warrior
Re: Sphere SFML v0.75alpha
Reply #191
N E O: looks good, I'll move to this style: <type name="x">value</type>.
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

Re: Sphere SFML v0.75alpha
Reply #192

Actually, I can't modify Jurassic to do that. I would need access to the [] operator (not the C# overload, but the JS one), which means adding to and modifying the parser so that a new Array type, the TypedArray, has the ability to get and set bits of an underlying buffer with the [] operator.


Huh, V8 allows you to overload the bracket operator (scriptside) of objects. It's a shame Jurassic doesn't have the same feature. Perhaps you could add a .at() member (like std::strings in C++...God knows why they have it) that performs the same function as brackets would?

I only push this because it is kind of native JS (well, kind of future native JS).

  • Radnen
  • [*][*][*][*][*]
  • Senior Staff
  • Wise Warrior
Re: Sphere SFML v0.75alpha
Reply #193
Well... There might be a way I'll go ask the creator, see what he thinks. It might be buried somewhere...
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

Re: Sphere SFML v0.75alpha
Reply #194
Do you have a link for json2.js?