Skip to main content

News

Topic: Ludum Dare (Read 9774 times) previous topic - next topic

  • DaVince
  • [*][*][*][*][*]
  • Administrator
  • Used Sphere for, like, half my life
Re: Ludum Dare
Reply #45
Something I just learned...



...Ah well. I'll just comment on it, then.

  • DaVince
  • [*][*][*][*][*]
  • Administrator
  • Used Sphere for, like, half my life
Re: Ludum Dare
Reply #46
I found a blind spot! You can just stand here and keep pressing the space bar. (Until I won and accidentally skipped the "You Win" message, anyway :P ).

  • Radnen
  • [*][*][*][*][*]
  • Senior Staff
  • Wise Warrior
Re: Ludum Dare
Reply #47

"This application has failed to launch because zlib1.dll was not found. Re-installing the application may fix this problem."


I have no clue what you are trying to do. Just extract into a new folder and play. It's really not that hard... Why are you always running into these DLL errors???


I found a blind spot! You can just stand here and keep pressing the space bar. (Until I won and accidentally skipped the "You Win" message, anyway :P ).


That's from the dumbed-down enemy AI. They used to perfectly find you, but only a single enemy could go on screen since it was too slow. The A* pathfinder was impossible to speed up in Sphere.

Performances of Pathfinders in Sphere:
- Kamatsu's (A*, priority queue): 950ms to traverse 100*100 map.
- Radnen's (A*, binary tree): 600ms to traverse 100*100 map.
- Beaker's (DFS): 400ms to traverse 100*100 map.
- Radnen's (sorted list + table lookup): 200ms to traverse 100*100 map.

These are remarkably slow. In a better language these should be magnitudes faster, especially the binary tree and priority queue, which should be near instantaneous for even 100000*100000 sized maps (due to log performance). I fully expected the sorted list version to be the slowest. Sphere just can't handle - at all - any complex data structures. I remember when Kamatsu made a quadtree in Sphere and couldn't get it to do something smart (pixel collision in his terrain tech demo), because it was just way too slow, despite being a perfectly good and efficient data structure to use.

Therefore, I'm definitely going to add A* pathfinding as a stock function call straight into Sphere-SFML.
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: Ludum Dare
Reply #48
I wonder if the performance optimizations in typed arrays could help here? Although just using a modern JS engine (which you'd need for typed arrays) would probably be hugely beneficial in the first place.

  • DaVince
  • [*][*][*][*][*]
  • Administrator
  • Used Sphere for, like, half my life
Re: Ludum Dare
Reply #49
That is really too bad. Figured it had to do with the pathfinding, but I also thought I needed to let you know so you could add some blockable thing on tiles like those, maybe. (Bug fixes after compo is over are allowed)

Hmm, wouldn't these make good benchmarks for testing in TS and SSFML? Just so you can see the benefits already (and diagnose performance problems, if any). :)

  • Mooch
  • [*][*][*]
Re: Ludum Dare
Reply #50

Something I just learned...



...Ah well. I'll just comment on it, then.


Aww, what? Sucks.



"This application has failed to launch because zlib1.dll was not found. Re-installing the application may fix this problem."


I have no clue what you are trying to do. Just extract into a new folder and play. It's really not that hard... Why are you always running into these DLL errors???


Hey, it's not my fault. I downloaded the zip, I unzipped it into sphere/games/Cellar Rush, I double-clicked "game.exe," it threw an error at me. I tried opening the game in the Sphere 1.5 editor and running it from there, too, (which I had to do with another Sphere game that wouldn't work from it's exe). That didn't work, though.

Maybe it's my system, or I have a virus or something. I'm on an Acer netbook, if that means anything. Windows XP Home SP3, N450 CPU @ 1.66GHz, 1.66 GHz 0.99 GB of RAM.

I'll try downloading it to another computer later and let you know if it works there. Then we'll know if it's my machine.

  • Radnen
  • [*][*][*][*][*]
  • Senior Staff
  • Wise Warrior
Re: Ludum Dare
Reply #51
Well, Windows should be able to find dependent DLL's in the root directory of the executable. I double checked the zip, it's definitely there. You are using XP though, which is scary since it's old and not supported anymore (sorta until early next year, that is) by Microsoft. It is a nice game though. How is it you can't play this game, but other games? Oh, and this one is released with Sphere 1.6, it may not work at all in 1.5.
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

  • Mooch
  • [*][*][*]
Re: Ludum Dare
Reply #52
Didn't get a chance to check it on my other machine, but I can already guess what went wrong -- somehow, the zip must've downloaded incompletely or something, because my zip doesn't have zlib.dll in it (checked all the folders, too).

Ah, yep! Downloaded it again, works now.

  • N E O
  • [*][*][*][*][*]
  • Administrator
  • Senior Administrator
Re: Ludum Dare
Reply #53

Performances of Pathfinders in Sphere:
- Kamatsu's (A*, priority queue): 950ms to traverse 100*100 map.
- Radnen's (A*, binary tree): 600ms to traverse 100*100 map.
- Beaker's (DFS): 400ms to traverse 100*100 map.
- Radnen's (sorted list + table lookup): 200ms to traverse 100*100 map.

These are remarkably slow. In a better language these should be magnitudes faster, especially the binary tree and priority queue, which should be near instantaneous for even 100000*100000 sized maps (due to log performance). I fully expected the sorted list version to be the slowest. Sphere just can't handle - at all - any complex data structures. I remember when Kamatsu made a quadtree in Sphere and couldn't get it to do something smart (pixel collision in his terrain tech demo), because it was just way too slow, despite being a perfectly good and efficient data structure to use.

Therefore, I'm definitely going to add A* pathfinding as a stock function call straight into Sphere-SFML.


I'll tell you what: I agree with you wholeheartedly and feel that having some pathfinding written natively into the engine for speed and exposed to the API is important enough that I will make an official recommendation for conditional pathfinding to be written into future versions and forks of the Sphere engine, starting as soon as possible. The conditions are:


  • Pathfinding must be built into the map engine on a pixel level and a tile level (ie, TWO map engine pathfinding functions exposed in API, one for pixel level and one for tile level); ALL obstructions (sprite, tile, AND obstruction lines) must be taken into account in both cases, possibly with a toggle to ignore/not ignore triggers and/or zones in the calculations
  • Non-map engine pathfinding must be available anywhere else (ie, pass some network mapped obstruction list, start and end points, and return...something, probably the "shortest path" as an ordered array of nodes or something)
  • Any working pathfinding algorithms may be used, but we could probably conditionally branch which to use based on list size vs performance vs whatever other factors like how FFTW conditionally switches FFT algorithms


So yea...pathfinding!

Re: Ludum Dare
Reply #54

Hmm, wouldn't these make good benchmarks for testing in TS and SSFML? Just so you can see the benefits already (and diagnose performance problems, if any). :)


I would like to try this.

I expect that simply using Jurassic and V8, with compiled JS and more advanced built-in optimizations, we will see at least an order of magnitude of improvement. I haven't seen any benchmarks for Jurassic, but V8 is known to handle large and complex data well. That's one reason it was chosen for Node.js.

  • Fat Cerberus
  • [*][*][*][*][*]
  • Global Moderator
  • miniSphere Developer
Re: Ludum Dare
Reply #55

I'll tell you what: I agree with you wholeheartedly and feel that having some pathfinding written natively into the engine for speed and exposed to the API is important enough that I will make an official recommendation for conditional pathfinding to be written into future versions and forks of the Sphere engine, starting as soon as possible. The conditions are:


  • Pathfinding must be built into the map engine on a pixel level and a tile level (ie, TWO map engine pathfinding functions exposed in API, one for pixel level and one for tile level); ALL obstructions (sprite, tile, AND obstruction lines) must be taken into account in both cases, possibly with a toggle to ignore/not ignore triggers and/or zones in the calculations
  • Non-map engine pathfinding must be available anywhere else (ie, pass some network mapped obstruction list, start and end points, and return...something, probably the "shortest path" as an ordered array of nodes or something)
  • Any working pathfinding algorithms may be used, but we could probably conditionally branch which to use based on list size vs performance vs whatever other factors like how FFTW conditionally switches FFT algorithms


So yea...pathfinding!


Isn't pathfinding in pixel space incredibly difficult due to the sheer size of the search space?  From what I understand that kind of precision generally requires the use of waypoints or something similar, and that would require revamping the map engine, no?
miniSphere 5.0b1 (stable: 4.8.7) - Cell compiler - SSj debugger
Forum Thread | GitHub Repo

  • Radnen
  • [*][*][*][*][*]
  • Senior Staff
  • Wise Warrior
Re: Ludum Dare
Reply #56
It is possible to do that in pixel space with a gradiented pathfinder. I think part of my issues with pathfinding thus far in Sphere is that you can't expect pathfinding to go that fast, unless you use a very smart method like jump point searching. Even with JPS, it's still a crutch: you need multi-tiered pathing to do anything of the sort. All state-search AI methods are about reducing the size of the state space. JPS helps cut the search down, but what about the actual size? Multi-tiered pathing can help you find a broad, coarse path, which in turn is subdivided into smaller chunks, keep doing this until the pixel level and you should have a fast pathfinder (regardless you use JPS).

That said, pathing a 200x200 grid the old fashioned way should still be very quick, it's just that realtime, 'n' entity pathing is very hard, and made near impossible since you can't thread your code in Sphere.
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: Ludum Dare
Reply #57
You could still do calculations it breadth-first, per entity (each entity do x number of calculations per frame, where x is inversely proportional to the number of entities).