|
Posted By
|
Message
|
Pixelthief
Dedicated klik scientist
Registered
02/01/2002
Points
3419
       
|
1st April, 2011 at 17:18:44 -
Originally Posted by Johnny Look
Or you could just have a circular sprite with 600 pixels of diameter attached to the unit sprite and then check for collisions. If it's colliding, attack. Pretty simple I think. Alternatively you could just check for distance with the closest enemy unit much like you would if it would have been done in c or c++.
Ye haven't actually tried this, have you? Thats exactly what I'm saying doesn't work, as you scale up a game. A 600 pixel sprite will either not give you a proper distance value (square) or will require vast amounts of processing for the collision map (circle) that makes such a method extraordinarily slow past a few units. You can't create a game where 200 units are fighting 200 units using "circle detectors", it don't work. Thats ok for doing little platformers and flash games, but once you approach RTS's, you need to build the mechanics behind them soundly to scale it up.
One possible way is to sort all objects into two lists, one by their X value and one by their Y value, using a quick sort algorithm (note: I don't mean "quicksort" itself) to add/remove objects, and apply a search algorithm (ex, binary) to this sorted list within the bounds of a coordinate, in order to quickly retrieve a list of all objects within a specific range of a point, for use in attacks, AOE spells, orders, AI, etc.
What you cannot do is simply compare every unit to every other unit. That quickly gets you high polynomial time complexity algorithm. Every unit on the stage comparing to every other unit on the stage using a square root, 50 times per second in a worst case? Hah. Is that O(N^3) or O(N^4) or what?. Even using an approximation distance algorithm thats optimized like the min/max one, your game would fall apart as it scales upwards- too many units would make it slow the bejesus down, and "too many units" would be about 30.
If you want to build something like Starcraft, you have to look at how its programmed. You can't seriously think that they made their RTS by putting a big 600 diameter circle on a collision map for every unit every timer ticker
Anyway I think it's pointless to discuss if it can be done or not and why, this discussion will only end when someone shows if it can be done or not. I know it can be done in construct at least because I did a basic rts skeleton with it before. I'll try to find the source and post it here, if not I'll recode it again.
"Johnny, if he doesn't know what he's talking about then you most certainly do not.
Out of everyone on the site I'd have to say that Pixeltheif has the most knowledge on this subject."
Ahah sure. On what grounds do you base your opinion ?
Well, this is sort of "my job".
 Edited by Pixelthief
Gridquest V2.00 is out!!
http://www.create-games.com/download.asp?id=7456
|
GamesterXIII
Registered
04/12/2008
Points
1110
|
1st April, 2011 at 18:38:42 -
I can't believe I missed the whole part about the circular object.
Thats where theory and practical application come in to play. In theory it would work, but that is far from optimal as PixelThief has already pointed out.
Why do you think unticking "use fine collision detection" on large objects and perfectly square objects drastically speeds up MMF games? I guess you could get it to work if the game was tiny.
Edited by GamesterXIII
n/a
|
UrbanMonk
BRING BACK MITCH
Registered
07/07/2008
Points
49567
      
|
1st April, 2011 at 19:02:07 -
Originally Posted by Johnny Look
Alternatively you could just check for distance with the closest enemy unit much like you would if it would have been done in c or c++.
I had to laugh at that.
So, how would you know which one is closest if you don't know the distance, eh? 
Circular reasoning ftw!
n/a
|
Pixelthief
Dedicated klik scientist
Registered
02/01/2002
Points
3419
|
1st April, 2011 at 19:14:37 -
I'm actually curious how a game like SC or WC3 or SC2 finds their (objects in a radius). I think the approach of sorting object by x/y, searching over those lists, and then culling the circle-edged objects, would probably be so damn efficient it makes me imagine they did something entirely different, given how poorly coded many parts of those games were 
Of course that really gets into how costly the loop overhead is against executing a distance check- it gets down the fundamental idea of how many clock cycles it takes. Using a distance equation that takes an insignificant amount of time compared to elementary instructions on most hardware, this would be no more efficient than just iterating over all objects and checking their dist. But in an abstract sense it might be more efficient.
One thing you'll learn in computer science is that its very easy to write a program that will solve any computer problem. The problem is in solving them in any meaningful time and space (hey, look, the two themes of my indie project ^___^). A naive algorithm trying to solve an NP-complete problem might "guarantee" the right result, but it might take 7 billion years to compute and more memory then there are atoms in the universe. You can easily write an algorithm that will "solve" a 1024 bit RSA encrypted key message given a ciphertext and plaintext pair. Just iterate over all 2^1024 possible vectors. Your computer might blow up when the sun goes nova before then.
Its not hard to write an RTS "engine". Its hard to write one that will actually run in a meaningful way, where you can have large amounts of units all doing their pathfinding, collision detection, fog of war, AOE effects and so on all at the same time while running at 60 FPS on a modern personal computer. You *could* use a 600x600 pixel circle detector over all objects, and then I'd have to explain to you why that takes 600*600*N^2 loops to do collision detection on N objects.
Edited by Pixelthief
Gridquest V2.00 is out!!
http://www.create-games.com/download.asp?id=7456
|
Sketchy
Cornwall UK
Registered
06/11/2004
Points
1970
|
1st April, 2011 at 19:47:47 -
Honestly, I think the truth lies somewhere between what Pixelthief and Johnny Look are saying.
RTSs aren't an easy genre by any means (and circular detectors are certainly not the way to go), but I don't believe they're as bad as Pixelthief is making out, and I know from experience that some parts of what he has been saying are not right.
Anyway, all that's besides the point.
The original argument was over the value of a built-in RTS movement.
I would say that RTSs are generally *very* formulaic. You can look at the slew of C&C clones released in the mid/late '90s, and the unit selection / movement systems used in those games are every bit as similar as the movement engines used in different platformers.
As for it resulting in "cookie-cutter" games - well, I don't see anyone criticising StarCraft, which if we're honest, is just a C&C clone with a few extras tacked on.
n/a
|
Johnny Look
One Happy Dude
Registered
14/05/2006
Points
2942
|
2nd April, 2011 at 00:23:27 -
pixelthief: I don't know about MMF2 but I tried stress testing construct with over 1000 objects in a level in a 4 year old laptop with no major slowdown, if at all.
Anyway, that was the first thing I thought of, I never really tested it but even if that was the problem construct has a built in turret movement that checks for the closest entity within a specific range. If you want to see it for yourself there's a basic rts example that comes with construct.
urbanmonk: Perhaps because you don't necessarily need to ? 
n/a
|
Codemonster
Administrator
Klik & Play Expert
Registered
03/08/2008
Points
133
|
2nd April, 2011 at 00:26:23 -
Originally Posted by GamesterXIII
Originally Posted by Codemonster
Gamester - Absolutely not, I'm assuming you didn't understand my point. With that being said, even if I did wish to sell such a product, it would clearly be that way from the beginning, worth the money and without bugs that affect the core functionality of the product. Excellent critism though, from a guy whos claim to fame are two projects (with either minimal or stolen artwork) that, much like Scirra, are obviously buggy and not updated for huge amounts of time.
Hagar - Yes, that is precisely what I mean.
I was just messing with you, and i'd give you props if khan is completed whether I like it or not, but wow you're an idiot. I never "claimed fame" over my unfinished projects, or anything for that matter. The projects aren't being worked on, you're right about that, but the art is far from stolen. The art in the game with the frog was 100% done by me in very little time. The first screenshots of Eden (the really bright colored one) contained my art (everything but the character/bird) , a friends art, and ONE sprite taken from zelda which was mentioned and replaced as soon as my friend got around to it. I just needed something with flying animations to see if the movement looked alright - that is probably the first time I've ripped a sprite since I was 9. The screenshot with the large sprites was 100% my friends artwork.
I hate to pull the jealous card, but why would you go so far as to claim that some half-assed mediocre artwork is stolen? Not to mention neither engine had any bugs in it as I refuse to release or show anything with bugs. The only thing I remember ever being "wrong" with Eden that wasn't really a bug was a misaligned hotspot that made it look like you were floating off the side of a platform. Something that I, frankly, dgaf about as that can be fixed at any time.
Consider suicide
Sorry- I must have hit a nerve lmao
--
Jesse J
|
GamesterXIII
Registered
04/12/2008
Points
1110
|
2nd April, 2011 at 00:40:04 -
lol
n/a
|
Johnny Look
One Happy Dude
Registered
14/05/2006
Points
2942
|
2nd April, 2011 at 00:45:19 -
By the way, I hope it's clear that I agree with you when you say that mmf2 or construct aren't the best way of making a rts. It's definitely not. But to make even a really simple rts in c++ you need to have quite some knowledge in quite a few areas, but to make the same thing in construct or mmf2 is much simpler but when going past that everything gets harder.
I know it is possible to make a starcraft or warcraft clone in construct and I believe that, at least in theory, it should work in mmf2 too.
My point being, if you are not fluent in c++ and don't know jack about pathfinding then construct or mmf2 are both viable alternatives if you're not too ambitious.
n/a
|
Pixelthief
Dedicated klik scientist
Registered
02/01/2002
Points
3419
|
2nd April, 2011 at 04:42:37 -
I think you really need to understand the underlying algorithms for how these "closet object finding" and "aoe effect" mechanics work. Like I said, its very easy to build something- its harder to make it *work*. While you can put together an RTS engine that will work on paper, it will fall apart at the seams as you start scaling upwards with it. Inefficiencies compound, and you need to have built upon a firm base to make the whole structure stay standing.
For example, that "turret movement" that finds the closet object may need to iterate across every single object in your stage and run a fast loop to calculate the distance and compare. And when you have N objects with turrets comparing 50 times per second, you will have N^2*50 comparisons going on; having 1000 objects on screen will lead to 50,000,000 distance checks, which may take 20-50 clock cycles on architecture compared to basic operators that take 1 cycle. You end up doing 2.5 billion cycles per second just to find distances between objects, not even accounting for the overhead of the structure, overhead of the compiler, overhead of the game itself and overhead of the CPU. Now how that translates into machine code and architecture is beyond me, or anyone on this planet really, but one thing I can tell you is: It will be slow. A single core might run at 2.27 GHz
Now these numbers are meaningless- they are gross simplifications of much more complicated architectures. But the point is simple. If you try to naively make an RTS with an inefficient architecture, it will fall apart as it grows. You either have to make it stay small, or know what you're doing, or else use someone else's architecture and make it a complete "paint by numbers" game like RPG-maker.
MMF2/Construct can be great for small flash games and platformers and bat'n'balls and so on, because they are small and not resource intensive. But attempting to build a fully functional moderate sized RTS in them is like building a house with 3 car garage out of tinker toys. Its not impossible, but it would probably take more work than actually learning how to build a house the right way.
Gridquest V2.00 is out!!
http://www.create-games.com/download.asp?id=7456
|
Hagar
Administrator
Old klik fart
Registered
20/02/2002
Points
1692
|
2nd April, 2011 at 17:36:55 -
I have never understood why MMF is so painfully slow even in fast loops, but this is the plague of high level languages.
Many people at uni use Python and Matlab to do data processing, which takes hours. My first matlab based analysis application did. I re-writ it in C , and the processing now takes about 20 seconds. My point? Trying to make an RTS in MMF is kind of like placing a bet on a 3 legged horse. It could win, but the odds of it winning are low.
By the way many modern processors can do many instructions and MAC's per clock cycle. Some i7's can do over 40 instructions per clock. A run of the mill core 2 duo can theoretically do 22.4 ( double precision) or 44.8 Giga FLOPS (single precision floating point operations per second), not that you will ever get there performance wise.
An RTS should be trivial computationally wise for any modern PC, given efficient algorithms and an efficient language.
My radius finding algorithm would be to first use a rectangular bounding system, and create a list of objects falling within this rectangle. Then calculate the distance to each object on this list (upon finding them) using trigonometry, and then create another list with objects falling under the distance desrired. I think this should be fairly quick, as you would optimising out units which are bound to be outside the desired radius and only performing the "heavy" arithemetic on plausible objects.
(in reality i would only use one list, but conceptually thats the algorithm)...
My job: DSP/High speed instrumentation researcher , re-writing "slow" C functions in hand optimised assembly is part of life for me. I can beat a C compilers optimiser in terms of cycles per iteration. Writing assembly is unfortunately more involved though, as you must consider how many cycles each instruction will take before the result is stored in a register.
And remember, if you see NOP in assembly, it stands for NOt oPtimised! 
n/a
|
Sketchy
Cornwall UK
Registered
06/11/2004
Points
1970
|
2nd April, 2011 at 18:54:00 -
Well, the easiest and most efficient system would be to just not check every object every frame.
I mean seriously, if a tank comes within range of a turret, sure the turret should notice - but does it really need to notice within 1/60th of a second?
And of course, you could just put a cap on the number of units allowed.
eg. "Age of Empires" limits you to 50 units, which improves both performance and gameplay - http://artho.com/age/bruce50.html
I guess my point would be that there are lots of ways to get acceptable performance, that don't require some complicated algorithm.
Sure you might not be able to make an RTS to rival "StarCraft", but so what? I don't see anyone here making platformers to rival "Super Mario World" either, and that's supposedly an easy genre to make.
n/a
|
Pixelthief
Dedicated klik scientist
Registered
02/01/2002
Points
3419
|
2nd April, 2011 at 20:22:49 -
Originally Posted by ..::hagar::..
I have never understood why MMF is so painfully slow even in fast loops, but this is the plague of high level languages.
Because MMF2 is a very high level intepreter. When you have a fast loop, it simply adds that many lines of MMF2 code to the event tree. So when you have a loop that reads 50 times, it will just parse that same event 50 times in a row; it wont shortcut and reduce that event to its elementary actions and repeat them based on jump statements or anything like C->Machine code would. Its a very, very high level language with tons of overhead.
Many people at uni use Python and Matlab to do data processing, which takes hours. My first matlab based analysis application did. I re-writ it in C , and the processing now takes about 20 seconds. My point? Trying to make an RTS in MMF is kind of like placing a bet on a 3 legged horse. It could win, but the odds of it winning are low.
By the way many modern processors can do many instructions and MAC's per clock cycle. Some i7's can do over 40 instructions per clock. A run of the mill core 2 duo can theoretically do 22.4 ( double precision) or 44.8 Giga FLOPS (single precision floating point operations per second), not that you will ever get there performance wise.
An RTS should be trivial computationally wise for any modern PC, given efficient algorithms and an efficient language.
Well see, thats the key- given efficient algorithms, efficient language. And then yes, they can be trivial. But you really need both. An inefficient language may not be able to pull off efficient algorithms. I just did a project on hash chaining in C that took 4 hours to execute in C, didn't even get 1% done in that time on python, and in MMF2 may have taken many solar ages.
My radius finding algorithm would be to first use a rectangular bounding system, and create a list of objects falling within this rectangle. Then calculate the distance to each object on this list (upon finding them) using trigonometry, and then create another list with objects falling under the distance desrired. I think this should be fairly quick, as you would optimising out units which are bound to be outside the desired radius and only performing the "heavy" arithemetic on plausible objects.
(in reality i would only use one list, but conceptually thats the algorithm)...
Mind thats still an O(N^2) algorithm for N objects comparing to N objects. Its probably the exact method that games like Starcraft use, checking in a rectangle and then culling in the ellipse. But I think an approach that uses a sorted list could vastly reduce the time complexity by not requiring a comparison on every single object. See, you'd have to compare every single object against that rectangle, and while the math is trivial its still an O(N^2) process. If you used a sorted list that ticked up once in each direction until it found the rectangle edges and culled from there, I imagine you could pull off an N*Log sort of complexity.
My job: DSP/High speed instrumentation researcher , re-writing "slow" C functions in hand optimised assembly is part of life for me. I can beat a C compilers optimiser in terms of cycles per iteration. Writing assembly is unfortunately more involved though, as you must consider how many cycles each instruction will take before the result is stored in a register.
And remember, if you see NOP in assembly, it stands for NOt oPtimised!
Yeah, its easy in theory to say that a distance algorithm will be 'costly' compared to elementary arithmetic, but I'm not expert on hardware or low level instructions. And I imagine theres cases where the cycles used in instructions is irrelevant due to overhead. For example, the approximation algorithm for distance thats in sketchy's examples is actually slower in MMF2 than just plain sqrt(dx^2 + dy^2), because of the huge overhead on the MMF2 interpreter. And I don't know how that applies to stuff like C and its square roots in the math library.
But one things for sure- you have to have at least some moderate idea of what you're doing. If you're comparing collision by iterating over a 600x600 collision map on every single object against every single object, it doesn't matter what hardware or language you're using- its going to suck. RTS's spiral upwards so quickly that it definitely matters to have some grasp of efficiency.
Yeah like Sketchy says, its not going to be worst case scenarios 60x per second per object against all objects. Modern RTS's use all sorts of methods for conserving computation- pathfinding might be done a single time per movement and then save its movement, timer ticks control how often something checks for radius, many RTS's cap units. But in something like MMF2 or construct which are so high level, even these small amounts of units with conservative computations still spiral upwards incredibly fast. Pathfinding is costly. Fog of war is costly. Radius grouping is costly.
Gridquest V2.00 is out!!
http://www.create-games.com/download.asp?id=7456
|
Arima
Registered
07/05/2004
Points
1
|
3rd April, 2011 at 03:20:17 -
Hey guys. Arima (disclaimer: a moderator) from the scrira forums here. Thought I would mention a few things:
First of all, the licensing model is not a subscription. You buy the program, it's yours. It doesn't expire like a subscription would.
The reason for the purchase the program and get two years of updates model is because the developers want to have a continuous development model. Instead of purchasing construct 2, then waiting for construct 3 and paying for the upgrade when it's completed, construct 2 remains in continual development and releases numerous smaller updates more frequently. This way you get new features continuously instead of having long gaps of waiting between versions.
If you think about it, it's not really all that much different from the normal model, where you buy a .0 upgrade and then receive free updates until the next .0 upgrade - and .0 upgrades often can take a year or more to arrive.
As for Scirra not completing C1, it was a good idea in my opinion. C1 wasn't designed as well as it could've been, and made things like making extra exporters prohibitively difficult. Since they started on C1 they've had industry programming experience and have learned a ton. It would have taken far longer to improve C1 than it would have for them to simply start over from scratch. Having used both C1 and C2 at very early stages of their development, the difference is like night and day. C1 was barely useable at the start, C2 is quite stable with very few issues.
Even still, it is possible to complete a medium sized project in C1. I'm doing it myself. There are some quirks and bugs you have to learn to navigate around, but a lot of programs, including MMF and game maker, have quirks that you have to learn to navigate around as well.
Pixelthief - something I don't think you realize is that construct's behaviors are coded in C plus plus (why don't plus symbols show up in the post preview?), making them much faster than events. As an example, I made a quick test that has 2000 sprites on two teams 'battling' each other. Using the turret behavior, on an older processor (AMD athlon 64 x2 4400 plus), having each sprite check for the closest enemy sprite every tick, I'm getting 150 frames per second. So that's 2000 sprites each checking for the closest of 1000 other sprites 150 times per second on an older processor. Behaviors are quite fast.
n/a
|
Hagar
Administrator
Old klik fart
Registered
20/02/2002
Points
1692
|
3rd April, 2011 at 12:56:19 -
Well thanks for the information pixeltheif . It has just put me off MMF even more .
Sketchy: Age of empires is quite old although sometimes I think limiting unit count is good for gameplay in an RTS. Makes strategy more important than just tank rushing (pick unit of choice relevant for the game ). I have no want nor desire to make an RTS either.
Just to back up Arima (and my argument) up, Supreme Comamnder can have 8000 units in play on a multiplayer map (1000 per player), and this cap can be upped with mods. My PC runs it fine, and it's 3D too so its inccuring a lot more computation than just a 2D RTS. Gieven a decent language and algorithms a 2D RTS should be compuationally trivial for any modern pc. If it's not, its due to the language or the algorithms used.
I fully understand what Sketchy and Pixeltheif are saying though, about MMF overheads, I have already done experiments with MMF (hence the horse betting analagy i used earlier).
n/a
|
|
|
|
 Post Reply
|
|
Advertisement
