At 1/7/16 02:27 PM, PrettyMuchBryce wrote: tricky performance problems

I'm curious. What performance problems are you having with a game that runs in a console window? That seems a little bizarre to me, but then again I haven't really made anything like that. I once got a nice tile-based multiplayer RPG-thing working well in AS3/AIR (at least the "multiplayer" and "tile-based" bits), but that's the extent of that. Only performance problems I had with that were regarding the way I drew tiles and utilization of the GPU.

At 1/7/16 09:58 PM, egg82 wrote: I'm curious. What performance problems are you having with a game that runs in a console window?

The performance problems are not on the front-end which is web-based, not console-based. The performance problems are on the backend server which processes all of the logic for the game. The game is completely server authoritative. When you have many thousands of entities in the game all trying to do pathfinding around a pretty large grid many times per second then you inevitably run into some performance issues. X_X

At 1/8/16 03:05 PM, PrettyMuchBryce wrote: The performance problems are not on the front-end which is web-based, not console-based.

Whoops! I mean, it looked console-based from your screenshots :P

The performance problems are on the backend server which processes all of the logic for the game. The game is completely server authoritative. When you have many thousands of entities in the game all trying to do pathfinding around a pretty large grid many times per second then you inevitably run into some performance issues. X_X

Ah, I see. I wonder how most MMOs do it? I mean, they have good servers but I'm sure there's a ton of performance tips in there as well. Maybe caching the paths wouldn't be a bad idea, either. I've been playing Guild Wars 2 a LOT recently and it seems my pet always takes similar paths to places. It also seems to try to predict where I'm going, so if I stop short it goes on without me for a few yards before it stops as well.

You're using a fast algorithm, right? Not something like A*? (Or at least a much more efficient variant of A*)
What about a hill-climbing algorithm? I think I posted about one earlier, I thought it was pretty cool and might actually be really efficient since you don't really need to find a path, just the next highest value. The only issue I can see with that is when the destination moves you'll need to re-calculate the values around it, unless either caching or some sort of buffer is involved. You may also want to pre-calculate hill-climbing values since unless the terrain changes they won't change.

At 1/8/16 04:06 PM, egg82 wrote: Ah, I see. I wonder how most MMOs do it? I mean, they have good servers but I'm sure there's a ton of performance tips in there as well. Maybe caching the paths wouldn't be a bad idea, either. I've been playing Guild Wars 2 a LOT recently and it seems my pet always takes similar paths to places. It also seems to try to predict where I'm going, so if I stop short it goes on without me for a few yards before it stops as well.

It uses coarse waypoints for general movement and then straight line or some radius based one for when it's near.

Bryce I know you were doing a bunch of pathfinding stuff like jps and all that, but why do you have to update the path multiple times per second? I think there's a more optimal algo that uses the previous step's astar traversal if the path needs to change assuming you're recalculating the whole thing each time.

At 1/8/16 04:18 PM, MSGhero wrote:

At 1/8/16 04:06 PM, egg82 wrote: Ah, I see. I wonder how most MMOs do it? I mean, they have good servers but I'm sure there's a ton of performance tips in there as well. Maybe caching the paths wouldn't be a bad idea, either. I've been playing Guild Wars 2 a LOT recently and it seems my pet always takes similar paths to places. It also seems to try to predict where I'm going, so if I stop short it goes on without me for a few yards before it stops as well.

It uses coarse waypoints for general movement and then straight line or some radius based one for when it's near.

Bryce I know you were doing a bunch of pathfinding stuff like jps and all that, but why do you have to update the path multiple times per second? I think there's a more optimal algo that uses the previous step's astar traversal if the path needs to change assuming you're recalculating the whole thing each time.

I have explored quite a few options here. The other important thing to remember is that with caching-based solutions you are eventually bounded by memory. So right now the world is 400^2, and caching every possible path would lead to out of memory errors here. (~12.8 billion paths using n choose k).

So we could be smart about caching some paths, but the tricky part is that the entities in the game do block, and they also move around a lot. So this means that you can find a path that can later turn out to be blocked (because something moved in the way of it).

I do use A* as it's the fastest algorithm that suites my needs. I can't use JPS because I need tile costing.

The destinations of the entities are always changing, as are their positions. So doing something like dijkstra maps is not an option.

I recently implemented HPA*, which divides parts of the world into regions, and caches paths between the regions. The issue here is that the region and adjacent region edges need to be recalculated if the collision information changes within the region. In my case this happens whenever an entity moves. This actually turns out to be less efficient overall, because entities are moving a lot more often than I am calculating paths.

At the moment I have made big strides by parallelizing the pathfinding operations over multiple cores. This is done by having all of the units take their turns simultaneously and then resolving the conflicts synchronously afterwards. This way I am theoretically bounded by the time it takes for the slowest entity to take it's turn. To give you an idea of the timescale I'm working in, my goal right now is to keep each turn under 5ms.

If you guys know of other algorithms that I am not aware of then feel free to link me to the paper and I will take a look. :)

At 1/8/16 04:47 PM, PrettyMuchBryce wrote: If you guys know of other algorithms that I am not aware of then feel free to link me to the paper and I will take a look. :)

The only other things I can think of are to use diffusion maps to pathfind or to not pathfind every entity at the same time/delay the search to like once every tenth of a second. http://gamasutra.com/blogs/TylerGlaiel/20121007/178966/Some_experiments_in_pathfinding__AI.php

At 1/8/16 05:09 PM, MSGhero wrote:

At 1/8/16 04:47 PM, PrettyMuchBryce wrote: If you guys know of other algorithms that I am not aware of then feel free to link me to the paper and I will take a look. :)

The only other things I can think of are to use diffusion maps to pathfind or to not pathfind every entity at the same time/delay the search to like once every tenth of a second. http://gamasutra.com/blogs/TylerGlaiel/20121007/178966/Some_experiments_in_pathfinding__AI.php

The other other thing is do you really need the _optimal_ path? Like if 0,0 pathfinds to 399,399, you know that path will be invalid in like 5 seconds. Maybe scale the distance down to a max of X and pathfind to that tile before pathing to the next step until the goal.

At 1/8/16 07:44 PM, MSGhero wrote: The other other thing is do you really need the _optimal_ path?

This, although I had the very slightly different idea of finding localized paths to increase performance. You don't REALLY need the best path for each calculation.

Like if 0,0 pathfinds to 399,399, you know that path will be invalid in like 5 seconds. Maybe scale the distance down to a max of X and pathfind to that tile before pathing to the next step until the goal.

This is a good point. Also I like MSG's earlier response on how MMOs pathfind with a global point system and then localized lines when it comes down to details. Of course, pathfinding isn't really my forte, but I like to think I know a bit about multiplayer and server performance. (Did I ever mention how much ridiculousness I had to pull out of my ass for this to work on a cheap, shared server?)

Also, Dual_EC_DRGB with the default constant and a 32-bit nonce is the best RNG and we should all use it.

Said nobody respectable ever.

At 1/8/16 07:44 PM, MSGhero wrote: The other other thing is do you really need the _optimal_ path? Like if 0,0 pathfinds to 399,399, you know that path will be invalid in like 5 seconds. Maybe scale the distance down to a max of X and pathfind to that tile before pathing to the next step until the goal.

This is actually not such a good solution. I think you would realize this quickly if you started to implement it.

First off how would you decide on a shorter path ? Do you just guess based on, say, the half way point ? There is no such thing as "scaling the distance down" with A*. You recursively search neighbors until you find the destination. You could stop after some number of iterations and choose the point with the best heuristic distance, but you may end up with a point very far away, or in the wrong direction entirely of your destination depending on the layout of the map.

Another problem, what if our final destination is in fact not reachable at all ? How would we figure that out before we started moving the unit toward the shorter point in the first place? Well, we could try to pathfind to the final destination, but doesn't that then defeat the whole purpose of the scaled distance solution, as we already have the final path ?

It's not all about movement either. What if the unit needs to decide which nearby enemy to attack. He needs to figure out which of them are reachable from his position. Maybe some are in an enclosed structure, or blocked by other units. How do you use your scaled-down solution to solve this problem ?

Also as I mentioned before, dijkstra maps don't work well when the destinations are constantly changing. The article you linked seems like a bad solution for this reason.

I think it's probably going to be difficult to solve the problem remotely without knowing all of the requirements, and seeing the actual implementation. I do appreciate the suggestions, though. :)

I don't know how to delete posts, so I edited it to say this

At 1/19/16 11:53 PM, GeoKureli wrote: I don't know how to delete posts, so I edited it to say this

Eyy.

But anyway, Sam and I made a plan to make a UI lib and editor in haxe that don't suck. I realize this may be impossible or even contradictory, but if any of you would like to help or offer input, it will be welcomed. I think step 1 is pinpointing why flixel-ui, stablexui, haxeui, etc all suck to use.

At 1/20/16 01:11 AM, MSGhero wrote:

At 1/19/16 11:53 PM, GeoKureli wrote: I don't know how to delete posts, so I edited it to say this

Eyy.

But anyway, Sam and I made a plan to make a UI lib and editor in haxe that don't suck. I realize this may be impossible or even contradictory, but if any of you would like to help or offer input, it will be welcomed. I think step 1 is pinpointing why flixel-ui, stablexui, haxeui, etc all suck to use.

It would be really funny if my original post was more useful than I thought when I removed it. But what exactly are you looking for? Simple reusable behavior or UI layout tools. For the latter I just use DAME. because every time I hardcode a position of something, I die a little inside.

Looking through my current project, which definitely has more UI than game play. The actual UI takes up a very little number of lines; most of the code is all the choreography of UI. Fade in this, tween these in with a stagger, followed by whatever that is, swooping up and giving that other thing a high five. Even with super compact greensock lib calls it's still most of my program.

Also hi all.

http://www.engadget.com/2016/01/20/ubuntu-linux-tablet-with-desktop-mode/

"Let's take a free tablet OS that was ported from the free desktop OS of the same name and put it on a $400 tablet, add $250 worth of hardware to it, and turn it into a much less powerful tablet PC with all the added quirks/bugs of a USB hub running on micro-USB!"
Fucking genuis, guys. Well done.

I forgot

At 1/7/16 09:02 AM, Innermike wrote:

btw is omar still around? haven't talked to him since 2013

Now how crazy is that. I haven't checked this thread in at least 2 years, and just randomly decide to do that today and this is what I stumble upon.

Unless you've been posting that in every page in anticipation of this day. Then it's not so crazy I suppose.

I guess we're posting something about our desks? Attached: my top shelf

Life Update

I've also been doing real full-stack web dev work, and made some articles on Tuts+.

At 1/22/16 01:13 AM, OmarShehata wrote: I've also been doing real full-stack web dev work, and made some articles on Tuts+.

Omarrrrrrrrr. Those tuts reminded me that I wanted to ask you about your asset sheets. Have you used spriter, dragon bones, or spine before? Or were joe's anims simple enough that none of those were necessary? I want to get into art, but me frame by frame animating is haha yeah right. Bone animating seems "easier" or at least more fit for me, but I don't want to drop money if I won't end up liking the tool.

Algorithm question:

I have a big grid in a 2D array, and I want to convert it to nape shapes. One shape per tile kills memory, and shapes have to be convex (rectangular) polygons. What's a good way to minimize the number of shapes to make?

My first thought is to scan horizontally and make single-line rects, but for thin, vertical stretches, that's the same as doing one per tile. Algo run time isn't really important since this will be a frame 0 calculation, memory and collision step time are what I'm more concerned with.

At 1/22/16 01:50 AM, MSGhero wrote: Omarrrrrrrrr. Those tuts reminded me that I wanted to ask you about your asset sheets. Have you used spriter, dragon bones, or spine before? Or were joe's anims simple enough that none of those were necessary?

It was simple enough to work with just tweens.

After living in San Francisco for 5 months, I finally had a chance to bring my computer over when I visited the family in Chicago for Christmas. I just bought a desk last week. I haven't had time to get a proper chair or mousepad.

At 1/22/16 10:25 PM, GeoKureli wrote: After living in San Francisco for 5 months, I finally had a chance to bring my computer over when I visited the family in Chicago for Christmas. I just bought a desk last week. I haven't had time to get a proper chair or mousepad.

What kind of desk is it? This apt is furnished, and I won't have my own own place for a while, but I'll invest in a desk where my computer, monitor, mousepad, keyboard, and tablet can all coexist.

Edit: I've never seen this before

At 1/22/16 11:21 PM, MSGhero wrote:

At 1/22/16 10:25 PM, GeoKureli wrote: After living in San Francisco for 5 months, I finally had a chance to bring my computer over when I visited the family in Chicago for Christmas. I just bought a desk last week. I haven't had time to get a proper chair or mousepad.

What kind of desk is it? This apt is furnished, and I won't have my own own place for a while, but I'll invest in a desk where my computer, monitor, mousepad, keyboard, and tablet can all coexist.

Edit: I've never seen this before

http://www.amazon.com/gp/product/B001FB5LE8
just over $100 is a steal, IMO. What's great is it's 2 desks that can be separated. My next apartment will likely be smaller, and then I can probably turn it into a 2 piece mini-desk/night stand.

Separate Info:
someone just started a game mechanics wiki, which is genius. The original classification he used is dumb, but I would really love to see a community get behind this.

At 1/22/16 11:21 PM, MSGhero wrote: Edit: I've never seen this before

I've had that happen to me damned near a hundred times. I vaguely recall liljim saying it was some kind of timing issue or race condition or something on their servers, but I'm not really sure. (It's certainly a bug, though.)

At 1/22/16 10:25 PM, GeoKureli wrote: After living in San Francisco for 5 months, I finally had a chance to bring my computer over when I visited the family in Chicago for Christmas. I just bought a desk last week. I haven't had time to get a proper chair or mousepad.

lawn computer chair, color me impressed. drink holder and everything

At 1/23/16 08:19 AM, Luis wrote: lawn computer chair, color me impressed. drink holder and everything

Rotated to most impressive angle:

At 1/22/16 10:25 PM, GeoKureli wrote: After living in San Francisco for 5 months, I finally had a chance to bring my computer over when I visited the family in Chicago for Christmas. I just bought a desk last week. I haven't had time to get a proper chair or mousepad.

You're in SF now too ? We should meet up and grab a beer sometime.

At 1/25/16 01:50 PM, PrettyMuchBryce wrote: You're in SF now too ? We should meet up and grab a beer sometime.

Yeah, Scott told me you were here. We should all catch up!

Edit: Forgot to say what I came here for.

Haxe project/lib layout. right now I've got one project with source/com.geokureli.krakel(my engine) and all my games in the same project such as: com.geokureli.baseball or com.geokureli.greed. I do the same with all my flash projects. that way to switch games I just change the document class (or in haxe, the project.xml).

I'm wondering if this is bad, if my games should be separated, or if my engine should be separate and referenced, should I isolate it and submit it to haxelib? The engine is nothing special, but is that the way haxe was intended to be used?

I adore how in the last 8 years since I joined this site as a young ambitious yet eccentric artist, the world has grown so much giving young kids these days to do so much more. Communities, forums, mentors, etc... all are here. Seeing someone from this site have their work on a consul market is something to be proud of. It's evidence that each one of us have the potential to make something great for all to enjoy... Peace a love bros.

And yeah, I'm like Jar Jar being Darth Plagueis... I've never left this site. Just been in the shadows watching.
Doing this and that, here and there.

May the Mullet be with you. :3

At 1/25/16 11:35 PM, GeoKureli wrote: I'm wondering if this is bad, if my games should be separated, or if my engine should be separate and referenced, should I isolate it and submit it to haxelib? The engine is nothing special, but is that the way haxe was intended to be used?

Idk about haxelib, but I have my shared code in github. Then "haxelib git linkname.git reponame" or something like that will keep that lib updated when you update your libs without necessarily being a haxelib. You could also set an external src folder in project.xml, but I've never tried that.

If you haven't seen this yet, take 10 minutes out of your day to do so. Totally worth it :D

Yo! If you are keen on checking out a site a friend of mine did on flash games, check it out here. A proper Finnish nerd!