Jump to content
  • Advertisement

Kasper Fauerby

  • Content Count

  • Joined

  • Last visited

Community Reputation

240 Neutral

About Kasper Fauerby

  • Rank
  1. Kasper Fauerby

    What Is A Scripted Event?

    In terms of gameplay you could also think of some features that are "core gameplay elements" such as enemy AI, picking up goodies, pulling levers to open doors etc. So when you run around a level, trying to shoot the bad guys, they will behave in a semi-intelligent manner that can be different for each playthrough (although it'll probably be a quite predictable behaviour). They'll do this by using the core game mechanics. Whenever the game needs something more complex and interesting (usually to further a story or something) the game designers will insert a "scripted event" where they take full control of the game world and game characters to make them do something that is so complex that the core game mechanics isn't enough.
  2. Kasper Fauerby

    A question about CRC32

    Thank you for all your suggestions and ideas. It seems like my original estimate of the risk of collision was fairly accurate after all, even though it also could appear that short strings, like identifiers, actually behave fairly well. I'll now have to decide whether 1% risk of collision is too much (in which case I guess I could just use a 64bit crc) or if it's acceptable for the scripters. I hope it did not appear that I was lazy when describing the problem, but I actually made a concious choice not to talk too much about the context of the problem, to keep focus on what I originally asked for: the probability of clashes, using different hash functions on identifier strings. It's not that I'm unwilling to talk more about the context, but I belive that would belong in the scripting forum :) But I guess I should have mentioned that this is not something I need for a completely new technology. It's an improvement to an existing scripting language in an existing game engine, and thus I'm working within a certain time frame and does not have the luxury of making a complete redesign of the system. We have a system where each identifier needs a unique id. Currently these are assigned in an incremental fashion, but this leads to certain problems that I'm trying to fix. So I have to look at the problem like this: Find a better way to generate a unique ID for a set of different strings. The crc algorithm has the very nice property that the ID will depend only of the name of the variable, not on the order in which the variables are detected by the compiler/engine (like it is the case when assigning incremental IDs). This is why my question was focussed on a very specific mathematical problem - the estimation of risk of collisions, given that I use crc32 as hash function. I also agree that, from an academic point of view, any solution with a non-zero risk of collision is unsatisfying. But sadly I have to take a more practical approach to the problem, and in this case I think it is acceptable to ask the script programmer to rename a variable of message - if this happens very very rarely (like once or twice in an entire game production cycle). Regarding the strings: The language is case in-sensitive, but since I don't like to work with identifiers this way I simply covert all identifiers to lower-case at parse time. So, an identifier consists of lower-case letters, underscores and numbers. There is no enforced limit to the length of the identifiers, but I guess I could introduce one - as long as its quite high. Generally I do not like to restrict the script programmers in this way though. I'll look into the Radix 26 suggestion and read up on the concept of perfect hashes. Best regards, Kasper
  3. Kasper Fauerby

    A question about CRC32

    Thank you for your replies, but I *do* need to save the values and use them across many machines, so memory addresses etc. will not work. I really need a (persistent) unique key for each string :) So, back to the original topic, Damon gave a probability figure that was radically different from the one I arrived at. I'm not sure I agree with his way of calculating it though, so if anyone else could verify his result it would be much appreciated. Alternatively, if you think crc in general is ill suited for the problem I'm trying to solve, I'm open for suggestions to other hash functions that will generate unique keys for different strings. - Kasper
  4. Kasper Fauerby

    A question about CRC32

    Hi guys, Here's a question for the math-experts, since my own probability math skills are a bit rusty :) My problem is that I need an algorithm to give me a unique number for each member of a set of strings (variable and function names in a scripting language). The set can be quite large for a full game - for example, 10.000 different names or something in that order. I need the number to be unique, so there can be a one-to-one mapping from a variable name to a number. Furthermore the algorithm must give the same number every time it is called on a specific string (obviously). So, I've pretty much decided to use a CRC algorithm - but I need to figure out if a crc32 is good enough or if I have to use a crc64. If a clash occur it would not be completely fatal, but annoying since I would have my script compiler ask the user to rename the offending new variable/function. This should obviously only happen very very rarely - and hopefully not at all. So, assuming a set of 10.000 strings I've tried to estimate the probability of a clash if I only use 32 bits for my crc. Here are my thoughts on the problem: When the first string is inserted there is 0% risk of a clash. When the second string is inserted there is a 1/2^32 risk of a clash, next we have 2/2^32 risk - and so forth. This gives me a total risk of: Sum(1, 10000) / 2^32 = 5000*10000 / 2^32 = 0.0116 So, assuming my math is correct, there is 1% risk of a clash when using crc32 on a set of 10000 strings? My question then is: Is the calculation above correct? Or am I way of track here :) Thanks for reading! - Kasper
  5. Kasper Fauerby

    Terrain Quadtrees

    In a quadtree each node or "box" should fully contain all it's children, so the y-values of a "branch" should simply be the min and max y-values of all its children. You could do this in a depth-first recursive function that returns the min/max y-values of the current node. A leaf would then simply return the min/max y-values of all its points, a "branch" would return the min/max y-values of all the results it got from calling on its children. The return value of the root node would be a bounding box for the entire terrain. - Kasper
  6. Kasper Fauerby

    Ellipse/Plane Collision equation?

    You can easily use pieces from the algorithm in my document to do what you are after - in fact one of the first steps in detecting collision between a swept sphere and a triangle is to detect whether the swept sphere intersects the general *plane* in which the triangle lies. In the case where you're looking for a static intersection test (ie. if the ellipsoid does not move) then it's very simple - transform to "eSpace/unitsphere-space", calculate distance from the center of the unit sphere and the plane, if abs(dist)<1 then your ellipsoid intersects the plane. - Kasper
  7. Kasper Fauerby

    d3dx9_24.dll etc. Missing

    Or, you could consider if you really uses anything from the latest releases of the SDK - and if not, go back to using a relase from before they introduced this .dll hell. - Kasper
  8. Kasper Fauerby

    Singleton Question

    Singletons can be great for many things, but they do not do what you think they do based on your question. What you need is the 'extern' keyword. In the header file you declare your array of textures like this extern GLuint Textures[nr]; This simply means: "when you (the compiler) see this line by including the header file then you should simply accept that an array 'GLuint Textures[nr]' will be available somewhere when the linker needs them" Then in *one* of the .cpp files (preferably the .cpp file matching the header) you have to actually declare the array like this: GLuint Textures[nr]; Now all files that include the header will know and use the same global array of textures that you have declared. - Kasper
  9. About the overhead; Yeah, that's exactly what I'm talking about. Of course it all depends on the scope of the engine you're creating. You need a pretty big scene tree before you'll see the overhead - probably a larger one than you'll create in any of your test scenes if you're not doing a full game. So it might very well be that you could ignore the overhead. On the other hand, assuming you do this as a learning process and with the intent of doing something that *would* be good enough for a full game (and I guess most hobbyists around here develop game technology for exactly this reason) then you might as well think of this problem now :) One way to avoid the overhead could be to extract certain nodes to different lists. So for example you might have a list called: 'UpdateEveryFrame' where you add all nodes in the scene that needs to have their update function called every frame. Then you might have another list called 'UpdateThisFrame' that nodes can put themselves into (or be put into) if they want/need an update this frame. This second list you process each frame after you process the 'UpdateEveryFrame' list - but you clear it every frame after you've processed it (do a 'while not empty' loop instead of a for-loop as nodes in the list could add new nodes to the end of the list). This is *one* way to avoid the traversal overhead but as I mentioned it introduces other problems. - Kasper
  10. @Paic: Overall your design sounds pretty good but you should be careful not to do too many "visits" of nodes that doesn't need to be visited. For example, if your scene-graph contains many nodes that should not/can not be rendered then it could introduce quite an overhead to visit them in the graph each frame to collect nodes for rendering. The same goes for an "update" pass through the graph - if you have many nodes that does not overload the update function from a base class (for example) then it'll be an overhead to visit them each frame. The overhead could come from the additional traversal time as well as the fact that you'll visit more memory and thus probably get more cache misses. We just release our first 3d game for PC, PS2 and Xbox and one of the things we'll change for the sequel is exactly the way we traverse the scene graph. For this game we did it pretty much the way you described - but we have many "logical" nodes that are only used to implement some level design or to group nodes ("folder" nodes in the tree). There are several ms per frame wasted by doing a full tree traversal compared to when we extracted certain nodes to linear lists that we have beside the scene graph. For example we have a list of all those nodes that we know we'll call "update" on each frame and so on. For rendering we have a seperate tree that contains only the sub-tree of the scenegraph that are the nodes that can be rendered. But you also loose some power by using extracted lists. For example it's harder to control the order of updates or for one update to trigger the update of its nodes children. Regarding the sorting: this should *definately* be done after the visible nodes has been retrieved somehow. Why? Because different rendering techniques or even different rendering passes will want to sort the nodes/geometry-bits differently. Hope this helps a bit.. - Kasper Fauerby
  11. Kasper Fauerby

    DX10 question

    I'm not sure about input and sound - but the graphics part will be quite different from what we have now. The concept of 'caps' will go away - which also means that DX10 will *only* run with hardware created for DX10. They are also doing some major changes to improve performance and interestingly the overhead cost of a DP will go down a lot.
  12. Kasper Fauerby

    Skeletal Animation Question

    Yeah, the fact that artist started to animate individual fingers instead of the good old "look as I wave my wooden box around" really upped the bone count :) But now, at our studio, we've also begun doing simple physics stuff on some extra bones to do pony-tails, ties, breasts, bellies and even hair. That stuff also eats up bones like they were snacks... :) - Kasper
  13. Kasper Fauerby

    World Creation System - Where to start?

    Not to scare you off or anything, but it *really* sounds like you should try and team up with a skilled programmer! The skills you seems to have - those of a technical artist - are skills that are becomming more and more important in the game business because it requires both technical and artistic skills to design a really cool game editor with a practical work flow for the users. Programming is really cool (I'm a programmer myself) but as other people has mentioned it is also a field that takes *years* to become great at. I'm afraid that if you start this project of yours all by yourself then you'll eventually become very frustrated that you cannot express your ideas in code - or your implementation will be limited compared to your visions. I was lucky enough to team up with a technical artist years ago and we met when we were both at the same level! Together we've been around first doing a "Wolfenstein 3D" engine in DOS, then up to a simple DirectX game (Tetris) in Windows and finally a full 3d game engine with its own integrated editors, plugins etc. This has really been perfect for both of us and we probably owe each other the fact that we now both have jobs in the game industry (actually in the same company) :) But if you are already at an advanced point on the "art side" and "team up" with yourself as a programmer at the "Wolfenstein in DOS" level - then it just won't work out! But if you are skilled as an artist and have nice ideas - then I'm sure you can find an equally skilled programmer to help you with your visions. Whether or not my words sounds like wisdom I'll leave for you to decide - but those are the words I'll offer :) - Kasper
  14. Kasper Fauerby

    Skeletal Animation Question

    Yeah, I'm having a hard time keeping the bone count down - our animators basically just wants as many as its technically possible for me to handle :) Since I'm doing skinning in vertex shaders I had to impose an upper limit of 70 bones and they kinda accepted that (with some grumbling :) Anyways, Alex, since you brough up the topic of terminology; You can think of skeleton animation as consisting of two parts - animation and skinning. Animation means the setup of the bones... you animate those based on some recorded animation track (key frames) from some animation tool. Once you've animated the bone setup you 'apply' them to a mesh - this is called skinning. So animation is the first step you do and it will always happen on the CPU. Skinning, on the other hand, can be done either on the CPU or on the GPU using a vertex shader. If you do the skinning on the CPU you don't have to pack any special data into your vertex format but if you're using a shader you'll have to pack the weights and skinning indices into the vertex format somehow. - Kasper
  15. Kasper Fauerby

    ellipsoid normals

    The normal to a point on a regular surface (like an ellipsoid) can be found like this: N(p) = (f'x(p), f'y(p), f'z(p)), where f is a function for all points on the surface. If f is the function f(x,y,z) = (x^2/a^2 , y^2/b^2, z^2/c^2), where (a,b,c) is the radii of an ellipsoid then the set A = {(x,y,z) | f(x,y,z)=1} defines all points on the surface of the ellipsoid. From the above we see that we have to differentiate f: f'x(x,y,z) = 2x/a^2 f'y(x,y,z) = 2y/b^2 f'z(x,y,z) = 2z/c^2 So the normal to a point on an ellipsoid is: N_ellipsoid(x,y,x) = (2x/a^2, 2y/b^2, 2z/c^2) You might want to normalize that though... For fun you might notice how this also works for a unit sphere (where a=1, b=1 and c=1). In this case the formula becomes: N_sphere(x,y,z) = (2x/1, 2y/1, 2z/1) = (x,y,z) So the normal to a point on a unit sphere is the same as the vector going from origo to the point on the surface - which makes sense doesn't it? - Kasper
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!