Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Reelya]

Wrapping whatever data structure you decide on inside a light-weight class like I outlined is good practice in general. That way, all the specifics are in one place, and if you decide to use a vector or some other structure later, you just change the internals of the class.

For example if you later decide you should have used bounds-checking on your array, then rather than going all through your code adding bounds checking statements everywhere, you just modify the class' operator[] method to have the check inside it. This also makes it quick and easy to turn the bounds-checking on or off based on release build or debug builds. You can have the operator spit out asserts, throw exceptions or write to an error log. Once you're sure no errors ever occur you can then remove (just comment out or use ifdefs) the checking code to speed up the program. With 'vector' class you're stuck with whatever error checking code they implement, even if your app is rock-solid and never overwrites an array.

[i2amroy]

Anyway, I'll just say this again: Don't micro-optimize. For something like a roguelike you won't notice anything about the performance unless you start doing really dumb stuff. Keep the code neat and readable. Modern computers are fast.

This right here. Though as someone who has helped develop a rouge like for a while now I'd like to say that while your performance might not need to be perfect, your implementation should be free of hacks. You wouldn't believe the amount of problems that have been run into due to dealing with old hacky implementations of things. Readable, somewhat efficient, and free of hacks is what you want to aim for in most situations.

[Orange Wizard]

My problem is that because my programming knowledge is largely self-taught, I can't tell what constitutes a hack and what constitutes sensible practice.

[Willfor]

As a fellow self-taught programmer, I've long since come to the conclusion that basically every line of code I write is a hack.

[Soadreqm]

Speaking of tilemap arrays, I've been dabbling with some roguelike coding, too. A lot of the tutorials I've seen have instructions to make the tile class as small as possible to conserve memory, since you often have like 500² of them, but I don't really see any reason to store a whole array of tiles. An array of pointers to ten or so tile objects repeated over and over again would serve the exact same purpose, wouldn't it? I'm asking since it seems way too simple. Like, surely there has to be some benefit to creating and storing 500² individual tile objects, or nobody would ever do it, right?

[Gatleos]

So I have entities A, B, and C on a grid. A and B have an AI routine which tells them to path to C on the grid, then "attack" it. The problem I've run into is that A and B's AI routines need to store a pointer to C in order to track its movements and change the path if necessary, but to do this I have to decentralize ownership of that pointer.

When entity C runs out of health and runs its die() function, it needs to be removed from the master entity list. When this happens, the pointer(s) to it are invalidated as I just delete the object. So if entity A is the last to hit C before it dies, I can return a signal which tells A to untarget it. But when B's turn comes around, it still has C targeted.

The dumb solution is to just check the validity of the pointer every loop to make sure another entity hasn't triggered it to become invalid. I tried using shared_ptrs, but they just made my code messier and more difficult to understand. Can anyone think of a way I could organize this that would remove the need to update a bunch of pointers every time I need to remove an entity from the list?

Speaking of tilemap arrays, I've been dabbling with some roguelike coding, too. A lot of the tutorials I've seen have instructions to make the tile class as small as possible to conserve memory, since you often have like 500² of them, but I don't really see any reason to store a whole array of tiles. An array of pointers to ten or so tile objects repeated over and over again would serve the exact same purpose, wouldn't it? I'm asking since it seems way too simple. Like, surely there has to be some benefit to creating and storing 500² individual tile objects, or nobody would ever do it, right?

Well, usually you want to segregate "static" and "dynamic" data from each other. If the tile object has a state which will change often (like fluid levels in DF), you store that data in every tile. Otherwise, you stuff it in a static data type and just give each tile a pointer to one of those. If it needs to change into a different type of tile, just swap out the pointer.

[Skyrunner]

With 'vector' class you're stuck with whatever error checking code they implement, even if your app is rock-solid and never overwrites an array.

Minor nitpick, using [] to access a vector ignores error checking iirc.

[alway]

So in general, cache performance is most of what you should optimize for on things like tile operations so you don't die a death of a million papercuts. See Mike Acton's Data Oriented Programming talks  for that (there's tons on youtube, just search for them). This sort of optimization is what will give you huge gains in large repeating operations like those done on tiles.

Memory size is utterly unimportant so long as it doesn't adversely affect cache performance. The typical user has several GB of RAM, and hundreds or thousands of GB to page out to in disk if you really need it. Outside the performance cost of moving that data through levels of caching, memory is free.

The best way to get good cache performance for such things, in general, is incredibly simple. Take the data being computed with at the same time, put it in a plain old 1D array, and rip through that. Lots of random pointers are bad (very bad, in fact), lots of complex data structures is bad. For example:

Code: [Select]

struct Tile
{
    float height;
    float temperature;
    float humidity;
    float grassFlavor;
    float renderingSmell;
    float radioactivity;
    float willComeUpWithNameLater;
    float b;
};
If you sent an array of those structures into a function updating the temperature, assuming you had a large number of them, it would be slower than sending in only the data required for the temperature update as it would fill more of the cache quickly. Turning it into something like the following would actually be faster:

Code: [Select]

vector<float> TileTemperatures;
vector<float> TileRadioactivity;
vector<TileSansTempAndRadioactivity> Tiles;
Or just peeling apart the entire structure into such arrays and sending them as necessary. This will not only make your code faster, it will make it MUCH easier to see what is being used/modified/etc by your program. UpdateTemperature() takes a tile array? Huh, I wonder what that does. UpdateTemperature() takes temperature array and a radioactivity array? I bet that function uses radioactivity to increase the heat in a tile.

( Now coming back to the point about pointers being very bad for this sort of thing. That is actually conditional: If those pointers are to a small chunk of data, that data may stay in the cache and so be reasonably fast. However, if they are just random pointers to places in memory unrelated to one another, that will kill performance. As in, you will get less than 10% of your potential performance. )

Essentially, good code is just a matter of keeping things incredibly simple: fast iterations on flat arrays of data, as little jumping around between things in memory as possible, using only the subset of data you need. Keep things simple for the things you do the most and it will turn out to be optimizing for you. Optimizing simple things is Intel's job, so keep things simple and let them deal with it. Most bad code is the result of trying to be too clever for your own good. Even in cases where things like binary trees would be the 'optimal' data structure, for anything less than around 200 elements, just ripping through a 1D array is faster.


Edit: std::vector is generally fine because it is a relatively lightweight wrapper around flat arrays; additionally, it's a really simple data structure. If you need to maximize performance of it, you can trivially replace it later with your own essentially to-spec implementation. Most of the std:: containers are pretty bad; as such, most people will likely have their own personal versions of the important ones anyway.

And a fun fact about if statements and error checking: If statements are effectively free assuming the code goes down the same branch pretty much every time. Modern CPUs make extremely heavy use of branch prediction, allowing something which repeatedly passes or fails a test to be assumed to continue with that behavior, preventing it from slowing down the pipelining in the CPU and making it nearly free. When it fails to do so, it's called a branch misprediction, and that does incur some cost. However, error detection in particular should never take a different route (unless you have an error, in which case a mere 15 cycles of misprediction performance is the least of your problems). Additionally, the CPU is good enough at prediction that misprediction rate is something like 1% to 18%.

Now keep in mind that I just said 15 cycles. A cache miss? That's 200 cycles. You get one of those any time you access some random pointer which isn't near other data you're interested in. So that optimization I talked about above will speed things up several orders of magnitude more than removing a few if statements checking for out of bounds accesses to arrays.

[Reelya]

So I have entities A, B, and C on a grid. A and B have an AI routine which tells them to path to C on the grid, then "attack" it. The problem I've run into is that A and B's AI routines need to store a pointer to C in order to track its movements and change the path if necessary, but to do this I have to decentralize ownership of that pointer.

When entity C runs out of health and runs its die() function, it needs to be removed from the master entity list. When this happens, the pointer(s) to it are invalidated as I just delete the object. So if entity A is the last to hit C before it dies, I can return a signal which tells A to untarget it. But when B's turn comes around, it still has C targeted.

The dumb solution is to just check the validity of the pointer every loop to make sure another entity hasn't triggered it to become invalid. I tried using shared_ptrs, but they just made my code messier and more difficult to understand. Can anyone think of a way I could organize this that would remove the need to update a bunch of pointers every time I need to remove an entity from the list?

Each thing that can be targeted should keep a list of all enemies that are targeting it. Problem solved. If you come up with a decent set of methods for handling everything it won't complexify your code.

Make methods call setTarget and releaseTarget to handle adding and removing targets from the client (targeter) side. These methods should set the targeter's pointer but also make sure that the targeting information is correctly updated on the targeted side. For that, you'll need mirror image methods for the targeted object, maybe setAsTarget and releaseAsTarget. These will be called from their counterparts, and will need to have the "this" pointer of the targeter passed to them.

When something dies, you should iterate through the list and callback releaseTarget for each enemy. This will clear the pointer and also cull the entries on the targeted object. Just make sure you update the list iterator before doing the releaseTarget call or your list iterator willl become invalid and crash your program, since you're removing nodes the list in the middle of iterating through it. This will be the cleanest way to code the whole thing.

[MagmaMcFry]

So I have entities A, B, and C on a grid. A and B have an AI routine which tells them to path to C on the grid, then "attack" it. The problem I've run into is that A and B's AI routines need to store a pointer to C in order to track its movements and change the path if necessary, but to do this I have to decentralize ownership of that pointer.

When entity C runs out of health and runs its die() function, it needs to be removed from the master entity list. When this happens, the pointer(s) to it are invalidated as I just delete the object. So if entity A is the last to hit C before it dies, I can return a signal which tells A to untarget it. But when B's turn comes around, it still has C targeted.

The dumb solution is to just check the validity of the pointer every loop to make sure another entity hasn't triggered it to become invalid. I tried using shared_ptrs, but they just made my code messier and more difficult to understand. Can anyone think of a way I could organize this that would remove the need to update a bunch of pointers every time I need to remove an entity from the list?

Here's a very flexible approach: Excepting your master list, never actually store a pointer to an entity anywhere. Instead, store the target entity's ID in the targeting entity, and just retrieve the entity by ID from the list every time you need to look at it (I suggest storing the list as a hash map or something). If the target entity died, your lookup will return a null. It may be a teeny bit less optimized than Reelya's solution, but so much more legible and maintainable. You won't need to add new methods every time you add a similar mechanic, and most importantly your methods will keep intuitive responsibility (your die() method won't need to unregister all the relations, for example, and you can easily add new mechanics without having to edit your main entity class each time).

When something dies, you should iterate through the list and callback releaseTarget for each enemy. This will clear the pointer and also cull the entries on the targeted object. Just make sure you update the list iterator before doing the releaseTarget call or your list iterator willl become invalid and crash your program, since you're removing nodes the list in the middle of iterating through it. This will be the cleanest way to code the whole thing.

No it isn't, there are much cleaner ways. Never modify your master list while iterating through it. Just iterate through a temporary copy of the master list instead.

[highmax28]

I;m having trouble with coding my homework. I have no idea what it means by the error I'm getting with it saying "out of memory".

I think I made it more complicated then it should be, but I can't seem to get it working. Can I get some help?

Code: [Select]

<html>
<head>

</head>
<body>
<script type="text/javascript">
//Name: usernameValidator.html
//Author: Spencer Durette
//Date: 3/31/2015

//Declare variables
var username;

var validUser;
var index = 0;

//Prompt the user for a username

while (validUser != true) {
username = prompt("Please enter a username.",username);

while ((index < length.username)) {
index += 1
if ((isNumeric(substr(username, index, index+1))) && index!=0) {
validUser = true;
if ((isNumeric(substr(username, 0, 1))) && validUser ==true) {
validUser = false;
document.write("ERROR! You cannot have a character as the first character!");
}
} else {
document.write("ERROR! You need at least 1 number included!");
}
}
}

document.write("That is a valid username.")

</script>
</body>
</html>

[Dutrius]

At first glance, I'd say that you're incrementing index infinitely, but then again I don't now much about JavaScript or server-side scripting, so take this with a pinch of salt.

[Levi]

-snip-

length.username should probably be username.length, just from a quick glace.

[highmax28]

-snip-

length.username should probably be username.length, just from a quick glace.

Good news. Did this and the prompt closes when i hit enter. Bad news, the isNumeric() function doesn't work apparently...

[Levi]

isNumeric and substr I don't think are part of javascript normally.  Maybe you were looking at jquery methods?