• Content count

  • Joined

  • Last visited

Community Reputation

138 Neutral

About lefthandman

  • Rank
  1. Hashing to Multiple Unique Values

    Oh wait, is it that you take your (n-bit long) hash function result, do the perfect hashing precomputation on the k (n/k-bit long) chunks of the result, then immediately hash all of the k (n/k-bit long) chunks to new locations with the guarantee that they are unique new locations? Genius! That would seem to work, assuming that perfect hashing doesn't decrease the uniformity of the chunks and works for even the most random of input sets (literally randomly and uniformly distributed bits). Thanks ApochPiQ!
  2. Hashing to Multiple Unique Values

    Ok, well the domain for the current use case is currently limited to strings. I've got a murmur hash for strings that vary (in game PMs etc) and an FNV hash for those that don't (player status tuples in string form). However I've tried to keep the hash function a black box set of bits for as long as possible so that I don't have to rewrite my implementation for everything I use it for (not saying it's better than existing hash libraries, I'm just trying to get good at this aspect of cs and jumping head first seems reasonable). What I've read on the wikipedia article makes it seem like perfect hashing is a way to generate a hash function (such as FNV or murmur) for a predetermined set that maps the set into your hash table without collisions. That's not exactly what I'm going for here, as I simply want to hash to k unique locations in my hash table (per string) so that I can implement cuckoo hashing. Another way of phrasing what I'm looking for is to say that given a perfectly uniform hash function (one in which any result has equal likelihood with all the others) that spits out a result n bits long map that to k results each one being n/k bits long and not allowing any repeats. Even if this ends up sacrificing uniformity, the quality of no repeats seems useful from my perspective.
  3. Ok, so excuse me for being a nub but I'm not having much luck searching wikipedia/the web for an answer to my problem. I've been trying to implement a generalized cuckoo hashing schema with a scalable number of hash functions (this also has applications to my pre-existing bloom filter application if I can get this working). The problem I'm having is trying to "sample without replacement" in stats terms. I would like my hashes to all be unique locations in my table that way I don't waste time mapping twice to the same space. AFAIK this should also increase the uniformity of my functions since there are a triangular number fewer possibilities to choose from when sampling without replacement. I've got a nice hash function already, and the ability to generate enough uniformly distributed bits to hash k times, it's just that I'm having trouble with the uniqueness aspect. Thanks! Also, if any clarification is needed, I will most surely provide it.
  4. Programming Language

    I would recommend C. You'll find quite a few discernible differences from C++ beyond the lack of OOP. It's perhaps the most important language I've learned.
  5. Compile times?

    Hmm, well I think that a good place to start would be to check where you're hitting the #ifndef X guards in your files (I assume you have those), and try to avoid extra #includes. Also, try to use a tool like Hudson that compiles outside your personal computer. Oh, and make sure you're not doing stupid stuff like compiling boost (the whole thing) every time (unless you need to ).
  6. Although I have little experience developing for a mobile platform, I can *hopefully* assist you in choosing technologies that have the characteristics you've described. [quote] Resizing images is expensive(in terms of RAM & speed). IE, so can Android, iOS handle resizing 10+ images(for eg .png) & display them on screen in a relatively fast amt of time? In Mosync doing such stuff depends on the phone RAM but on HTC Desire(512mb) it takes about 6 seconds which is unacceptable for my app.[/quote] In general, raster graphics are not meant to be re-sized. For this reason, I would recommend you seriously consider using vector graphics. However, it should be possible to resize images fast even if they are in a raster format. The following could help, although it's written for Tcl/Tk: http://wiki.tcl.tk/11196 [quote]Does the API come with its own fonts & layout managers? Mosync doesn't have its own fonts, you have to create & import it & you cant change the colour of a font. You also cannot make the text in a widget display centred or word wrapped, can Android/iOS/other do this?[/quote] For a free font, I like DejaVu: http://dejavu-fonts.org/wiki/index.php?title=Main_Page Especially DejaVu Sans Mono. [quote]Is it a REAL headache designing your app layout because of all the different potential phone sizes there are, so the widgets placement & skins will be incorrect on small screens & images will be out of proportion on large screens? Does the Android/iOS/other API help you by automatically laying out your GUI no matter the phone size & does it automatically scale image widgets & fonts to suit phone sizes?[/quote] Yeah, I'd really suggest vector graphics.
  7. Task management

    @Emergent Maybe it wasn't you but I'm pretty sure I saw someone mention the hungarian algorithm on a different thread. That thread, you were spot on as it was about targeting (as in shooting stuff). The OP's post wasn't about choosing a task (as I took it), but rather what to do when the inability to get to something is permanent rather than temporally impossible. (also, the hungarian algorithm runs in O(n^3), and in games, I think if I want the optimal solution to a problem and I want a good framerate I'd rather just have a priority system where units have a priority factor in addition to specific tasks they look for automatically) As I see it, there are several types of tasks (in a game like the Sims): Tasks the user gives to the unit (if these fail, they should be removed from the list of tasks entirely, but when they are added, they should be of the highest priority) Tasks the environment gives to the unit (these should be given as follows. choose two units at random from your list of units and give the task to the unit with the least time till the end of queue + time to get to the other task, the unit chosen with the highest likelihood will be the unit with the least to do/most likely to do the task soon) (if these fail, check the environment, then repeat the selection process) Tasks the unit gives to the unit (iterate through all your units, check their needs, put their needs at either the front of the queue, aka self sufficient family, or right after the player's needs, gives more control to the player) If these can't be completed, just remove them entirely from the queue, but give the player a heads up.
  8. Dealing with (annoying) people (and their code)

    Oh my god. (not like you don't hear this everywhere on the internet already) Wow, you guys keep on giving me better and better advice! Yeah, I don't really care what they think. Ok, so what I will be doing next week (after having read all your insightful responses :) ) is trying to get better at just explaining things because there seems to be a general consensus that I should ignore these people and not give in to the dark side and bash them across the face with a verbal shovel. So yeah, basically when they blurt out something frustrating I'm going to ignore it and keep on talking. I'll also try and follow jbadams guidelines because they seem to relate highly to what I am doing wrong right now. I have a great teacher/mentor, and I'm really not taking advantage of that. He is probably the person I should be observing to better my explaining capabilities. Also, good tip about not talking for the sake of trying to fill any gaps in my speech, those gaps do seem really long to me and I'll try just enduring the agony for the sake of letting my mind slow down and think about what I'll say next. @d000hg: I'm talking about me (person who doesn't do TopCoder, but might try whatever his friends are doing to finally see what it's like this year) talking to person who may do TopCoder/USACO/other contests. My definition of viable solution is very different from his definition. This doesn't really change the fact that I have to teach them how to do useful things in blender/povray/python. Yeah, basically there's no right/wrong answer, it all depends on what's asked of you. However, I have a feeling I won't get very pretty code out of these people. "When I went to university I also had to deal with a couple of contest coders myself, but not a lot, fortunately. When they made assertions about something, I always asked them why, and got them to explain in detail. Generally this is the point where I could differentiate between coders who knew what they were talking about and those who didn't. Also, if someone says that you doesn't need to learn "xyz", because it's inefficient, always tell them that learning weak algorithms are just as important as learning the good ones, so you won't make bad design decisions later." - Tachikoma Quoted for truth. I think that this will work brilliantly because: a) It's a short answer compared to the alternative of proving the use of these algorithms to stubborn people. b) It gives me a way of truly knowing which of these contest coders I would have the most luck explaining things to. c) It lets me know when I'm logically wrong (aka, they actually answer correctly and prove that their assertion is valid). This is always a good thing, because it's not like every time I say something it's got to be correct. Sometimes some of their assertions might actually be truthful and I can't just rule them out because they give no explanation right off the bat. Also, Antheus has a good point in that these people probably don't represent all Contest Coders. The point of these competitions is to narrow down the field for potential employers. The ability to spot ~100 truly talented problem solvers is really useful. Also, to further prove his point, I have looked at some of these contests and they actually post the winning code. Yep, that means if these people are winning at contests these employers get to see the code that let them win (which is a really good argument for commented, nicely written code). Not going to generalize that statement to all of them, but for those contests that do do this, it just legitimatizes them further with me.
  9. Dealing with (annoying) people (and their code)

    Thank you for the replies. @Antheus: I'm a peer. The reason I have to teach them python is because I'm doing it as a part of a series student run initiatives inside our cs club. That said, this does put me in the role of teacher of around ten other students. I've never really become too active within the main branch of the cs club because I've been working on my own projects. Hence, no top scores within competitions to brag about (although I am doing several this year and hope to do well). @Samoth: Yeah. My sentiments exactly. I didn't really want to be too harsh because these were some of my first interactions with the guy. O() truly doesn't say much about how fast something runs, but in theory it should (since of course it is a measure of how costly-operations scale with the size of your dataset/other variables) @frob: That would be okay if I didn't have to teach ten people with similar mindsets today/every friday for the course of the year. I'm really only doing this because there will be around five people I am teaching who are really friendly and have things to share with me that I might not know about. It would be really nice if I could learn a good way of explaining things to these people such that they would get it, however: a) They like c code to the point where I'm going to have to give them c programs along with every python script (or include the c equivalent in the comments) b) They have... odd... beliefs about cs. Another such example is that someone in the class will most definitely try to look smart by pointing out every special case where what I say isn't true. I know this because I have been in a class with him, and he objected to every algorithm my teacher presented by basically saying "Well, if [precondition of the algorithm] wasn't there, it wouldn't work. oops!" (yes, he ended it in oops, always) c) I am classically bad at explaining things. Generally, I can't give an algorithm outright (in my words at least) to someone and have them understand it. I have to walk them through several examples of how the algorithm accomplishes its function (such as what I'm attempting here). @Tachikoma: True. True.
  10. Ok, so I've become sort of a lone ranger as far as coding goes. The main reason is my school is packed to the brim with contest coders, and I really can't stand the atmosphere they lend to programming. When talking to one of these contest coders I often find myself being talked down to, for instance: (this is the first time I ran into this guy, in fact I was having a discussion about priority queues before he butted in) Friend: So, what papers have you read lately? (I know, it's not the best for conversation but it was pretty late at night) Me (to friend): Oh, not much, I've just been trying to get a good feel for what the best priority queue is for various fields. I think they're pretty interesting. Contest Coder: (coming from nowhere) You think you know about priority queues? *ahem* Well, if you actually know about priority queues, you should have no trouble with the following problem... (goes on and on about a problem and the various time bounds I need my algorithm to run under, takes like 10 minutes)... oh wait, I forgot, you don't actually need priority queues for that one. Here, let me find the one I was thinking of... (whips out his laptop) Me: No, it's fine, I'll just do the "interesting problem" you just told me about. I get back to my dorm, and code it up. Next week. Contest Coder: So did you finish my problem? Me: Yeah, what's your- Contest Coder: Does it run under O(nlogn)? Me: Yeah, I'm pretty sure, I've just got to try and remember my algorithm, hold on. Contest Coder: You should ALWAYS remember the big-O times of algorithms you make. Me (thinking): ... I finished it 20 minutes after you told me the problem. Then a week passed, with me coding up other things. Me (talking): It runs in O(n) time. Contest Coder: Ok, can you email me your answer? Me: Yeah, what's your email? Contest Coder: (gives his email) So, what language is it in? Me: Java, because bluej makes prototyping really fast. Otherwise I'd have used c (knowing that most contest coders program in c). Contest Coder: Yeah, Java sucks. And I thought about it, you don't really need Priority Queues for anything. Me: Lol, good one. Contest Coder: Yeah, I'm serious, what algorithm needs a priority queue? Me: A*? Contest Coder: What's that? I bet it doesn't need a priority queue. Me: (Try to give an explanation with constant interjections by cc and eventually give up)... ok, I'm just bad at explaining things. This is the typical conversation I get from contest coders (usaco, acsl) that & they dismiss any work that's long term saying stuff like "oh, that's trivial" when my current line of research really isn't (oddly enough, bettering A*). Not to mention, when they ask for help on a bug they have, I open up their project and find it covered with global variables & branching (<- the newbs at contests mainly). I'm not saying all contest coders are bad, it's just that they should realize other ways of life, err, coding. What's the best approach if I now have to teach a lot of them how to use blender and povray, and after that python (for use scripting)?
  11. Pathfinding in pseudo-isometry

    I'd agree with steering behaviors as far as avoiding dynamic obstacles, but since I assume that the dynamic obstacles are what you are moving through the map, I'd use Greedy Best First Search for the static obstacles.
  12. Fog of war

    Ok, so I bet that you want at least a realtime algorithm, or at least something that runs quickly. http://www.appsizematters.com/ Has a good tutorial. The only thing I can add would be to use Run-Length Encoding to store the fog bits (if you have a decent-sized map).
  13. Drag racer AI [edit - code included]

    Ok, first off I'm going to clean up your code a bit. This will help both of us look at it and make determining what is causing your current problem a little bit easier. obstacle=checkforobstacle(x,y,distance*5,50); //idk if the flag is being used later on, so I'm simply going to make it perform the same exact way as it did previously... flag = 1; if obstacle { if isleftturnpossible&&!checkforobstacle(x,y-30,distance*3,40) { leftturn=1;rightturn=0; } else if isrightturnpossible&&!checkforobstacle(x,y+30,distance*3,40) { leftturn=0;rightturn=1; } else { flag=0; decelerates=1; } } Now about that leftturn = 1, rightturn = 0 part. Well, don't you only need one turn variable and a flag that states whether or not you're turning. Therefore it can be changed to lrturn(1 = left, 0 = right). Now about the mystery constants being used on checkforobstacle. If it's possible to decelerate, then why will distance*3 always be appropriate? And will you always be moving 30 (tiles?) at a time? Also, will you always be heading the same direction or will it be a circular track? Because if it's anything but straight, you might actually need to subtract 30 where you're adding it and visa versa. It gets even more complex if your turns change the direction you're headed which means you'll have to deal with angles. So in closing, I suggest the following: a) Clean up your code! b) Take a good look at your checkforobstacle function and make sure your coordinate system isn't screwing you over. Remember, three rights makes a left(once you've turned, turning again won't cause you to head in the same direction as the first turn). c) Post your checkforobstacle code, and maybe even your turning code. Anyways, here's the code I recommend you use... //idk if the flag is being used later on, so I'm simply going to make it perform the same exact way as it did previously... flag = 1; if checkforobstacle(x,y,distance*5,50); { if isleftturnpossible&&!checkforobstacle(x,y-30,distance*3,40) { lrturn = 1; } else if isrightturnpossible&&!checkforobstacle(x,y+30,distance*3,40) { lrturn=0; } else { flag=0; decelerates=1; } }
  14. Drag racer AI [edit - code included]

    Ok, so I'll start off this post with links to two websites that may be of interest to you. http://www.red3d.com/cwr/boids/ http://gamma.cs.unc.edu/RVO/ The above two may be a little advanced for you, but they are the current industry standard. If you want your script to work, check to make sure that: a. Your obstacles that it isn't avoiding are stored in your scene graph or whatever you are looking at when you're checking if an obstacle is in front of the player. b. You aren't explicitly stating to check for one kind of obstacle. Make sure you use the highest level class that describes "something to avoid" as what you're checking for. c. You don't have rounding errors anywhere near that section of the code. Make sure you always give coordinates the same type. d. IF none of these help you to solve your problem, post your code for us to look at. Now for the second algo. My basic understanding of what you've described is you're using recursive circles of perception to get from one 100 m line to the next. The thing is, if you want that to work, you'll have to know why the first one isn't working.
  15. Virtual Town

    Just as a word of advice, rather than simulating everything on the large scale I'd recommend going to the individual needs basis. This will get an end result that looks much more impressive and you can actually demo things other than #s going up and down for economy and such. For pathfinding, amitp's blog has basically everything you need to find out and more. http://theory.stanford.edu/~amitp/GameProgramming/ If you want to be lazy, check out the Recast & Detour libraries, although I doubt you'd need half of the features they include. Ok, so I understand that you may want cool stuff like a procedural terrain generator, and that's fine, but you've got to prioritize a little bit. I'd get a system (non graphical) where you've got a basic decision "timestep" implemented. I'd write it in the same way I would a physics engine timestep (Box2D should be a good frame of reference). Then I'd deal with what the AI actors are doing currently, and what they choose to do when they're done (remember, this all happens in the timestep). Some good places to look are: The generalized assignment problem (http://en.wikipedia.org/wiki/Generalized_assignment_problem) Another option would be to go to http://aigamedev.com/ and learn about finite state machines, fuzzy logic, and hierarchical task networks (the latter two are fairly advanced). Once you're done with the ascii version of your town, I'd go to making it graphical (this still doesn't mean anything fancy). If you're planning on making it 3D, I'd start it out being 3D but you better know what you're doing first. I wish you the best of luck on your endeavors. A couple small asides: -use OOP concepts. If you want the people in your game to be any different, I'd simply make them all have the same super class somewhere up the line, and override the methods in that class. -don't get side tracked. Trust me, I've seen ideas like this get shot down in the sky by overly perfectionist devs. -get help early on. If you're open to it, this would be a good time to go out and make friends with someone you didn't know outside of cs class and make this project a co-op. If no one is up to it or you don't want to share, I advise finding someone you think is fairly experienced in cs and using them for advice.